Data structure for set of intervals - query for all intervals contains given point We're given a set of $n$ intervals $[a_i, b_i]$, $i=1...n$.
I am looking for a data structure which makes it possible to query for all intervals that contain the point $x$.

My proposition is using two-dimensional interval (sometimes name is segment) tree.   Each query will take $O(\log^2 n + k)$ time, where $k$ is number of interval such that contains point $x$.

Is this correct?  Is there a better solution?

There are many algorithms for this kind of problem.  See, e.g., segment trees and interval trees.  The kind of query you mention is known as a "stabbing query".

A segment tree takes $O(n \lg n)$ space, can be built in $O(n \lg n)$ time, and can answer a stabbing query in $O(k + \lg n)$ time, where $n$ is the number of intervals and $k$ is the number of intervals that contain $x$.  An interval tree takes $O(n)$ space, can be built in $O(n \lg n)$ time, and can answer a stabbing query in $O(k + \lg n)$ time.  Segment trees are static: they can't be easily modified after they're created.  Interval trees are dynamic: you can insert or delete an interval in $O(\lg n)$ time.

Other data structures exist as well.  There are also generalizations to higher dimensions, though the running time gets worse in higher dimensions.


Can you connect an output from a logic gate to 2 or more logic gates or inputs? I have been given this diagram of a circuit:
https://www.google.com/search?q=full+adder+logic+gate&rlz=1C1CHBF_enCA831CA831&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjCjZzc_PbfAhXCj4MKHahtCvcQ_AUIDigB&biw=1536&bih=792#imgrc=GFIqfN5OgCdtRM:

The second XOR gate looks like its output is being connected as inputs of 2 different gates at the same time. Am I interpreting this incorrectly or is it possible to send the a single output to 2 gates simultaneously?

In circuit complexity, the fan-out of a gate is the number of gates its output is connected to (similarly, the fan-in is the number of inputs to the gate). A circuit in which all gates have fan-out 1 is known as a formula. It is known that some $n$-bit functions can be computed by circuits of size $O(2^n/n)$ but require formulas of size $\Omega(2^n/\log n)$. It is conjectured that polynomial size circuits can compute more functions than polynomial size formulas, but this conjecture, known as the $\mathsf{NC^1} \stackrel?= \mathsf{P}$ question, remains unproved.


Finding stabbing numbers for lines for a set of segments in the plane So we have a lot of line queries in the plane, and for each line query we want to know the number of segments that intersect that line (are stabbed by the line) for a given set of segments in the plane *(not necessarily axis aligned). The set of segments is fixed but the number of query lines could be large.  I was thinking about maybe dualizing the problem: Each line segment turns into either an infinite "bow tie" or a horizontal band, and then we can compute the overlay of this arrangement, counting the number of intersecting regions inside each cell. But even though this becomes a pretty nice data structure, query time is still an issue. Any thoughts on how to make preprocessing time and stabbing query time low, assuming there will be a "somewhat large" number of queries (the tradeoff between preprocessing time and total query time is somewhat a parameter in this).

Are you familiar with

  H. Edelsbrunner, H. A. Maurer, F. P. Preparata, A. L. Rosenberg, E. Welzl, D. Wood.
  "Stabbing line segments."
  BIT Numerical Mathematics.
  1982, Volume 22, Issue 3, pp 274-281.
  (Springer link.)

Google Scholar finds more than 100 papers that cite it.

One can use a segment tree data structure, or an interval tree.
Segment trees offer $O(\log n + k)$ query time, where $k$ is the number of segments intersected. Space complexity is $O(n \log n)$.


why quicksort can have a best big o notation of (n log n) I don't really quite understand why quicksort has a big $O$ notation of $(n \log n)$. I would like some help understanding what exactly $(n \log n)$ is, and then how it applies to quicksort.
Also in $(n \log n)$, what is the base for the $\log$?
Thanks.

The "standard" version of quicksort does not have a worst case time complexity of $O(n \log n)$. In fact, it can even require $\Theta(n^2)$ time. However, quicksort does have an average time complexity of $O(n \log n)$.
You can get quicksort to run in $O(n \log n)$ worst-case time if you use a suitable pivot-selection strategy. In particular you want a pivot-selection algorithm that requires at most linear time to find a pivot ensuring that the two recursive calls of quicksort are  performed on at least a constant fraction of the input elements. See Median of medians.
The base of the $\log$ doesn't really matter as long as it is a constant greater than $1$. This is because the big-oh notation hides constant multiplicative factors and if you consider two possible bases $a$ and $b$, you have $\log_a n = \frac{\log_b n}{\log_b a}$, where $\log_b a = \Theta(1)$. That said, $\log$ usually refers to the binary logarithm in computer science.


Guarantees on computing $a+x(b-a)$ in floating point I want to implement the function $f(x,a,b) = a + x(b-a)$ where all the inputs are floating point (doubles, say), such that (a) $f(0,a,b)=a$ exactly; (b) $f(1,a,b)=b$ exactly; (c) $f(x,a,b) \le f(y,a,b)$ whenever $x \le y$; and preferably (d) it is accurate (correct up to rounding) for $0 \le x \le 1$.

Implementing $f(x,a,b)=a+x(b-a)$ directly does not work because for example $f(1.0,-1.0,\operatorname{prev}(1.0)) = 1.0$ (where $\operatorname{prev}(a)$ is the floating point number before $a$). And $f(x,a,b)=b-(1-x)(b-a)$ has the same issue.

Now $$f(x,a,b) = (1-x)(a+x(b-a))+x(b-(1-x)(b-a))$$ has the first two properties.

Does it have property (c)?
How accurate is it?
Is there a more performant way to do this?

Here is a proposed alternative
$$f(x,a,b) = \operatorname{ifelse}(x<0.5, a+x(b-a), b-(1-x)(b-a))$$
which also satisfies (a) and (b), but it is not accurate near $0.5$. It also satisfies (c) except maybe at $\operatorname{prev}(0.5)$ and $0.5$.

For example with double-precision arithmetic we compute $f(0.5,-1.0,\operatorname{prev}(1.0))$ to be -1.11e-16 but it is actually -5.55e-17, so out by a factor of 2.

It's worth noting that the implementation proposed in the question gets this example correct.


Find $i$-th number in unsorted sequence in logspace (deterministic turing machine) There is given input - words is sequence of numbers:  $w_i$ is number
  in sequence, $i$ is position.   All of them are in written in binary
  system.

  $$w_1\#,...\#w_k\#i$$    Prove that there exists deterministic
  Turing machine which find $i$-th number in sorted sequence $w$ in
  logspace.

I am not sure if I correctly solved it, so I ask for checking my reasoning.  It seems to be fairly simple.

First of all, what we can do in logspace:
compare two numbers
iter over sequence (move to $n$-th number)

Simply,  we consider one by one each element of sequence and count how many elements is less than currently considered. If we count $i-1$ numbers, then we stop.  It requires logarythmic($k$) memory for counter.  These counter can be reused (for each iteration).

Waht do you think ? Maybe some other approach to proving it ?

First let's consider the case when numbers are unique. The idea is that for each element $w_t$ we count the number of elements in the sequence which are less than $w_t$. After each loop on all elements of the sequence we check if there are $i-1$ elements less than $w_t$ then $w_t$ must be $i$-th element in the sorted sequence, so we halt with the output equal to $w_t$.

proc(w, k, i)
 for t=0 to k
   counter = 0
   for j=0 to k
     if w[t] > w[j]
      counter = counter + 1
   if counter == i-1 then output w[t] and halt
end-proc

Now, if numbers are not unique then we have to count duplicates as well

proc(w, k, i)
 for t=0 to k
   counter = 0
   dups = 0
   for j=0 to k
    skip if j == t
    if w[t] == w[j]
      dups = dups + 1
   for j=0 to k
     if w[t] > w[j]
       counter = counter + 1
   if counter+1 <= i AND i <= counter + dups+1
     then output w[t] and halt
end-proc

  w[1] w[2] ... w[counter] w[t] w[t] ... w[t] ..
  \__________  __________/     \_____  ____/
             \/                      \/
 all elements less than w[t]   duplicates

Both procedures require only constant number of variables i, j, k, counter, and dups whose lengths are $O(\log(k))$. Your solution is similar to these algorithms so your approach is correct.


Demonstration that every finite set is computable What is the best demonstration that show that "Every finite set is computable"?

thanks

Given any finite set, it's trivial to write a program that accepts exactly the members of the set: just compare the input against each element of the set in turn.


What is the complexity class of this variant of Subset sum? Let's represent Subset Sum problem with binary arrays instead of numbers.
Example: given two-dimensional array

[1, 0, 0] (4)
[1, 0, 1] (5)
[0, 0, 1] (1)

is there set of one-dimensional arrays, sum of which is equal to

[1, 0, 0, 1] (9)

In this problem sum of bits in each position can have carry-over. If carry-overs are forbidden (bit positions are independent) and we ask instead: are there arrays which sums to

[2, 0, 1]

then what complexity class such problems belong to? In what papers it was studied?

This is NP-hard. The associated decision problem is NP-complete.

There are various ways to prove that.  For instance, there's a straightforward reduction from exact cover; let the target array be all-ones, and then you have an instance of the exact cover problem, which is NP-hard.

Your problem is an instance of multi-dimensional subset sum (or multi-dimensional knapsack), for which you can find algorithms and approximation algorithms in the literature.

Related: https://cstheory.stackexchange.com/q/19976/5038, How to find subset of vectors whose sum has certain characteristics, https://cstheory.stackexchange.com/q/21865/5038, https://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints


How do POMDPs and Dynamic Influence Diagrams differ? To give some perspective, first consider the following diagram comparing Markov Chains, HMMs, MDPs, and POMDPs (I'm not sure who to credit for it).

                    Fully observable          Partially observable
                _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
               |                         |                           |
    no actions |      Markov chain       |           HMM             |
               |_ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|
               |                         |                           |
    actions    |          MDP            |          POMDP            |
               |_ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|

Recall that an HMM allows us to model probability distributions over a sequence of observations. Bayesian networks (not pictured) are a generalization of HMMs which model conditional distributions over sets of random variables (see here for a description). When modeling a problem over time, one appends a time index to the model resulting in a dynamic Bayesian network.

A tool known as a dynamic influence diagram extends dynamic Bayesian networks to decision-making problems through the inclusion of actions that can effect the evolution of the problem.

My question is: how do dynamic influence diagrams and POMDPs compare? On the surface they seem like they are modeling the same problem type. What sort of problems are amenable to each tool?

I'll quote from the paper "Interactive Dynamic influence diagrams" (DIDs) by Polich and Gmytrasiewicz (AAMAS 2007):

  A dynamic influence diagram is a computational representation of a POMDP.

They continue soon afterward:

  DIDs perform planning using a forward exploration technique known as reachability analysis. This technique explores the possible states of belief an agent may be in in the future, the likelihood of reaching each state of belief, and the expected utility of each belief state. The agent then adopts the plan which maximizes the expected utility. DIDs provide exact solutions for finite horizon POMDP problems, and finite look-ahead approximations for
  POMDPs of infinite horizon.

To me this suggests that DIDs are, as the authors state, one possible representation of a POMDP, to which a specific look-ahead type solution method is related to. As look-ahead is limited to approximate solutions for infinite horizon POMDPs, this also suggests that DIDs can not represent every POMDP.


Trustless exchange without a third party Is there a cryptographic (or even not entirely cryptographic) way of exchanging objects between Alice and Bob that would not require a third party, and Alice and Bob would not need to trust each other? For example, Alice and Bob have Y and X objects (some information) and want to exchange them (in other words both Alice and Bob after transaction will have access to the set Y∪X). How can they do this directly to each other?
Is it possible to solve this problem, for example, using private keys, zk-proofs, etc? Is it possible to solve it in principle?
Thank you!

This is known as the fair exchange problem.  There's lots of research on the topic; see the link for an overview and starting point.


What is the decision version of independent set? I always read that finding an independent set of size $k$ in a graph is $\mathsf{NP}$-complete. However, this only requires looking for all combinations of $k$ vertices and this is a polynomial procedure of order $k$.

I know that we can reduce directly SAT to independent set, with $k$ the number of clauses.

The problem is that I can't grasp correctly, as in 3-COLORING or 3-SAT, the required format to study the complexity of INDEPENDENT SET.

What is the decision version of independent set? And why isn't $k$-independent set in $\mathsf P$?

The definition of the decision version of independent set is the following:

Given as input a graph $G = (V,E)$ and an integer $k \in \mathbb{N}$, does there exist a set of pairwise non-adjacent vertices $I \subseteq V$ of size $|I| \geq k$?

The problem is polynomial time solvable if you consider $k$ to be constant, i.e., you can solve the problem in time $\mathcal{O}(n^k)$ but we usually take $k$ to be a part of the input.  If you reduce an NP-complete problem to this problem, you will see that the $k$ is indeed unbounded.


Is there a limit on transition function compositions in NFAs? I want to prove regularity of a language that contains a known regular language $L$ using an NFA.

Say the transition function of the automation that accepts $L$ is $f$.

In my new transition function, is there a limitation on composition of $f$?
For example, can I make the following transition in the new function?

$$f'(q_i ,\sigma)=f(f(f(q_i, \sigma))))$$

If not, why?

You can define the transition function of an automaton to be whatever you want, as long as it's a function of the appropriate type, i.e., $Q\times\Sigma\to Q$ fora DFA and $Q\times\Sigma\to 2^Q$ for an NFA.

However, the composition you've attempted doesn't actually make sense.  Since $f$ is the transition function of an NFA, it has type $Q\times\Sigma\to 2^Q$. As such, you can't write $f(f(q_i,\sigma))$, since the argument of the outer application of $f$ is some subset of $Q$, whereas there are supposed to be two arguments: an element of $Q$ and a symbol from the alphabet.  So, for a double-composition, you probably need to write something like
$$\bigcup\{f(q,\sigma)\mid q\in f(q_i,\sigma)\}\,.$$
You can try to work out the triple-composition yourself.

But are you sure you want to do that? You're defining an automaton that says "Every time I read the character $\sigma$, I will do whatever the original automaton would have done if it read three $\sigma$s." As I said, you can make your automaton do whatever you want, but I'd be interested to know the context that makes this a sensible thing to do.


Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle.

Define the directed cycle mean cost to be $\frac {\{\text {sum of cost of arcs}\}} { \text {# arcs}}$.

Consider the LP:

  $\max \lambda$

  s.t: $p_i + \lambda \le p_j + c_{i,j}$ where $(i,j)\in \mathcal A$.

I've shown:

The LP is feasible.
If $(\lambda,p)$ is a feasible solution then the directed cycle mean
cost of every directed cycle is at least $\lambda$.
The LP has an optimal solution (doesn't contain a line and $\lambda$
can't be greater than the maximum cost).

Now, I want to show given an optimal solution to the LP, it can be used to construct a directed cycle with minimal directed cycle mean cost.

I really don't have a clue on how to proceed. I don't see how an optimal solution give me the required information ?

I traced the LP back to this article. Here you can find the answer to your question presented in Theorem 2.

It might be helpful to look at the dual problem of your LP. This is analyzed in the above paper in Theorem 1. In this dual program your variables are defined as variables $z_e\ge 0$ for the edges. Then they show that the optimal cycle is given by the edges for which $z_e>0$ in the optimal solution. Then you can use the complementary slackness condition. It follows that the tight inequalities in your program define the optimal cycle.

Note also that the author provide an interpretation for the variables in your LP. The value of $p_i$ of a vertex not in the optimal cycle denotes the "least length of the path from the vertex $v_i$ to the optimal cycle".


What problems are believed to have an efficient algorithm? Just out of curiosity,
What problems are believed to have an efficient algorithm, yet haven't been found such an algorithm for them?

This question came up to my mind after reading about PRIMES problem.

I hope this question is appropriate for this forum

Thanks!

I'll cover problems that are easy to solve (i.e. in $P$) and problems whose solutions are easy to verify (i.e. in $NP$), and some problems that are probably not, and try to explain why people think one way or the other.

Under standard complexity-theoretic assumptions, $P=BPP$, meaning that most randomized algorithms can be "derandomized" (this family of conjectures is called the derandomization hypotheses). You read about a specific example, PRIMES, and it is expected that that is an instance of a more general phenomenon. So for example, polynomial identity testing probably has a polynomial-time algorithm.

For similar reasons, it is conjectured that $NP=MA=AM$. See the Complexity Zoo for definitions of these classes). One language in $AM$ is graph non-isomorphism: the language of all pairs of graphs that are not isomorphic. Clearly its complement it in $NP$ (because you can check whether a purpurted permutation is in fact an isomorphism), so surprisingly the fact that two graphs are not isomorphic is something that is expected to be easy to verify given some proof. Yet (afaik) we do not know which $BPP$-language we have to derandomize to obtain this result. If $NP=MA$ or $P=RP$, then it is easy to verify that an arithmetic circuit is not minimal.

These sets, $BPP$ and $AM$ are (afaik) the "largest" classes of problems that are expected to collapse to $P$ and $NP$ respectively, meaning they are expected to be easy to solve, respectively, to verify.

So we do not know how to verify non-isomorphism yet, much less decide it (as in, solve it in $P$). Is it hard? Is it easy? Interestingly, if Graph isomorphism is so hard that it's NP Complete, then a widely believed complexity-theoretic hypothesis (that "the polynomial hierarchy is infinite") fails, so graph isomorphism is probably not NP-Complete. We do not know of any hypothesis that fails under the assumption that graph isorphism is easy, i.e. in $P$ or in $BPP$. The same goes for factoring: probably not NP-Complete, not known to be easy.*

Problems in this Wikipedia list of NP-Intermediate problems are not expected to be in $P$.

Linear programming has a polynomial algorithm if you only count the number of arithmetic operations ($+,-,\times$ etc). However, those arithmetic operations may involve numbers that are more than polynomially long, so the algorithm is called weakly polynomial. It is expected that there is an algorithm that doesn't suffer from this, called a strongly polynomial algorithm. For example, Mihály and Vempala [1] recently presented a plausible-looking candidate for such an algorithm.

*Scott Aaronson once quiped that factoring might as well be in $P$. It would collapse the world economy, sure, but it wouldn't collapse the polynomial hierarchy, so wouldn't be that impressive.

[1] Bárász, Mihály, and Santosh Vempala. "A new approach to strongly polynomial linear programming." (2010).


Natural occurrences of monads that make use of the category-theoretical framework Today, a talk by Henning Kerstan ("Trace Semantics for Probabilistic Transition Systems") confronted me with category theory for the first time. He has built a theoretical framework for describing probablistic transition systems and their behaviour in a general way, i.e. with uncountably infinite state sets and different notions of traces. To this end, he goes up through several layers of abstraction to finally end up with the notion of monads which he combines with measure theory to build the model he needs.

In the end, it took him 45 minutes to (roughly) build a framework to describe a concept he initially explained in 5 minutes. I appreciate the beauty of the approach (it does generalise nicely over different notions of traces) but it strikes me as an odd balance nevertheless.

I struggle to see what a monad really is and how so general a concept can be useful in applications (both in theory and practice). Is it really worth the effort, result-wise?

Therefore this question:

  Are there problems that are natural (in the sense of CS) on which
  the abstract notion of monads can be applied and helps (or is even
  instrumental) to derive desired results (at all or in a nicer way
  than without)?

Asking whether an occurrence of monad is natural is similar to asking whether a group (in the sense of group theory) is natural. Once you formalise something, in this case as an endofunctor, either it satisfies the axioms of being a monad or not. If it does satisfy the  axioms, then one gets a lot of technical machinery for free.

Moggi's paper Notions of computation and monads pretty much seals the deal: monads are incredibly natural and useful for describing computational effects in a unified way. Wadler and others translated these notions to deal with computational effects in functional programming languages, by using the connection that a functor is a data type constructor. This  adds the icing on the cake. FP monads allow a treatment of computational effects such as IO which would be extremely unnatural without them. Monads have inspired related useful notion such as arrows and idioms which are also very useful for structuring functional programs. See the Wadler link for references. FP monads are the same thing as category theory monads in the sense that for an FP monad to work the same equations need to hold --- the compiler relies on these. Generally, the presentation of the monad differs (different but equivalent operations and equations), but this is a superficial difference.

A vast amount of the work of Bart Jacobs, to take but one example, uses monads. A lot of work stems from coalgebra, which is a general theory of systems. One of Jacobs' (many) contributions to the area is the development of a generic notion of trace semantics for systems (described as coalgebras) based on monads. One could argue that the notion of trace semantics is natural: What is the semantics of a system? The list of actions that can be observed!

One way to understand monads is to first program in Haskell using monads. Then find one of the many good tutorials available (via google). Start from the programming angle, then move to the theoretical side, starting with some basic category theory.


Can a purely declarative language really exist? Wikipedia has several languages listed as declarative languages.  One of these languages listed is XSLT, which is a language for applying transformations to XML.

https://en.wikipedia.org/wiki/XSLT

As I understand it though, imperative languages say HOW to do something, while declarative languages only say WHAT to do and leave it up to the eg. compiler to figure out the imperative details.

In this light, since when writing XSLT we still say "Do transform A, then do transform B", it seems like we are still writing imperative code.

Furthermore, taking a language like C++ which is arguably imperative, it actually seems semi declarative because the optimizer can re-order instructions or, change algorithms.

In fact, a switch statement seems to be a declarative associative structure, with containing values known at compile time, letting the optimizer make the imperative details based on the type of data it stores.  It can do binary searching, jump tables, if/else if chains and more. http://www.codeproject.com/Articles/100473/Something-You-May-Not-Know-About-the-Switch-Statem

This leads to my question...

Is it possible to have a purely declarative language?  If so, what would it look like, and could an interpreter/compiler actually be made to convert anything into imperative machine code, beyond a no-op?

It also seems impossible to have a purely imperative language in modern days, as the CPU can do instruction re-ordering, speculative branch predictions, and similar, making your instructions more of hints as to what to do, as opposed to exact instructions of what to do.

Or am I completely off base here?

Declarative programming defined the goal, as in your example transform A to B, where steps made are not present in this layer of abstraction, and simply it is not enforced.

Imperative programming defines steps to achieve the goal. With optimizations it is a bit of mixture of both - steps are defined but this is translated to goal and then changed to make it faster.

To achieve exactly imperative in this pure form all optimisations need to be suppressed, branching does not change the order. Interpreter executing one instruction at the time does that already.

As far as I know we call languages like C, Fortran, Pascal, assembler imperative languages and do not go into details of execution. One example is read from disk 1bit, 1 byte, several bytes and so on - disk reads the whole batch at once so it did not exactly what we asked for, the same with access to memory.

The side effects are not declarative, but imperative. Purely functional language is declarative already. The problem with purely functional language is e.g. I/O, which is mittigated by monads, to set states, but it does not matter to declarative one.


Strassen's Algorithm proof I have been reading about the Strassen Algorithm for matrix multiplication.

As mentioned in Introduction to Algorithms by Cormen , the algorithm is not intuitive. However I am curious to know if there exists any rigorous mathematical proof of the algorithm and what actually went into the design of the algorithm.

I tried searching on Google and stackoverflow, but all links are only on comparing Strassen's approach to standard matrix multiplication approach or they elaborate on the procedure presented by the algorithm.

Note: The same question has been asked on https://stackoverflow.com/questions/19229454/strassens-algorithm-proof , but without any definite answers

The main idea of the algorithm is to find a way to multiply two $n\times n$ matrices with less than $n^3$ "essential" multiplications (multiplications of two elements of the matrices). This forms part of a larger theory, algebraic complexity theory. Here are a few highlights:

Every algorithm for multiplying two matrices can be formulated (at a small loss) as a bilinear algorithm: you form some linear combinations $\alpha_1,\ldots,\alpha_k$ of entries of the first matrix, some linear combinations $\beta_1,\ldots,\beta_k$ of entries of the second matrix, compute $\gamma_i = \alpha_i \beta_i$, and then every entry of the product matrix is a linear combination of the $\gamma_i$.
This can be formulated as computing the tensor rank of the matrix multiplication tensor $\langle n,n,n \rangle = \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n x_{ij} y_{jk} z_{ik}$. The tensor rank is similar to the more familiar matrix rank, and corresponds to the number of "essential" multiplications ($k$ in the preceding example).
Any non-trivial bound on $\langle n,n,n \rangle$ for any $n$ translates to a non-trivial matrix multiplication algorithm for all $n$, via the same recursive approach as Strassen's algorithm (this approach is also known as tensorization). There are several extensions, culminating in Schönhage's asymptotic sum inequality.
The asymptotic sum inequality can handle identities involving disjoint sums of matrix tensors (in plain English, ways of multiplying several matrices at once using fewer "essential" multiplications than the trivial algorithm uses), and can even handle "approximate" identities (border rank). Strassen came up with another method (the laser method) that can handle non-disjoint sums, and this led to the Coppersmith-Winograd algorithm and its descendants, which is where things stand today.


Reducibility of 2 boolean satisfiability problems I beg some help with this problem.

  There are 2 boolean satisfiability problems.

  Problem $A$: Determining whether an arbitrary formula of size $n$ is $satisfiable$.
  Problem $B$: Determining whether an arbitrary formula of size $n-1$ is $satisfiable$ in which $n$ is a positive integer $\ge 2$

  Prove that $A$ can be solvable if $B$ is solvable.

I guess the solution would be showing that $A$ is Turing-reducible to $B$. It means I have to show the oracle algorithm of $B$ derives the oracle algorithm of $A$.

As you see, the arbitrary formula of $B$ is $n-1$, but that of $A$ is $n$.
How can I suppose to entail the oracle algorithm about $A$ from the oracle of $B$, which is determining the formula of 1-less size than that of $B$?

Problem A is reducible to Problem B in following manner:

Pick a variable in problem A and set it to
0
Now we have a formula of size n-1, if satisfiable with B then return satisfiable
Else, pick problem A again and set the variable to 1
Now we have a formula of size n-1 again, if satisfiable with B then return satisfiable else return unsatisfiable

In other words: Split problem A into two problems B using any variable. If B says unsatisfiable for both 0 and 1 then it is unsatisfiable. If it says satisfiable for at least one of the two, then it is satisfiable.


How to approach Vertical Sticks challenge This problem is taken from interviewstreet.com

We are given an array of integers $Y=\{y_1,...,y_n\}$ that represents $n$ line segments such that endpoints of segment $i$ are $(i, 0)$ and $(i, y_i)$. Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, $v_1, ..., v_n$, where $v_i$ is equal to length of ray shot from the top of segment $i$. We define $V(y_1, ..., y_n)
= v_1 + ... + v_n$.

For example, if we have $Y=[3,2,5,3,3,4,1,2]$, then $[v_1, ..., v_8] = [1,1,3,1,1,3,1,2]$, as shown in the picture below:

For each permutation $p$ of $[1,...,n]$, we can calculate $V(y_{p_1}, ..., y_{p_n})$. If we choose a uniformly random permutation $p$ of $[1,...,n]$, what is the expected value of $V(y_{p_1}, ..., y_{p_n})$?

If we solve this problem using the naive approach it will not be efficient and run practically forever for $n=50$. I believe we can approach this problem by indepdently calculating the expected value of $v_i$ for each stick but I still need to know wether there is another efficient approach for this problem. On what basis can we calculate the expected value for each stick independently?

Imagine a different problem: if you had to place $k$ sticks of equal heights in $n$ slots then the expected distance between sticks (and the expected distance between the first stick and a notional slot $0$, and the expected distance between the last stick and a notional slot $n+1$) is $\frac{n+1}{k+1}$ since there are $k+1$ gaps to fit in a length $n+1$.

Returning to this problem, a particular stick is interested in how many sticks (including itself) are as high or higher. If this number is $k$, then the expected gap to its left is also  $\frac{n+1}{k+1}$.

So the algorithm is simply to find this value for each stick and add up the expectation.  For example, starting with heights of $[3,2,5,3,3,4,1,2]$, the number of sticks with a greater or equal height is $[5,7,1,5,5,2,8,7]$ so the expectation is $\frac96+\frac98+\frac92+\frac96+\frac96+\frac93+\frac99+\frac98 = 15.25$.

This is easy to program: for example a single line in R

V <- function(Y){ (length(Y) + 1) * sum( 1 / (rowSums(outer(Y, Y, "<=")) + 1) ) }

gives the values in the sample output in the original problem

> V(c(1,2,3))
[1] 4.333333
> V(c(3,3,3))
[1] 3
> V(c(2,2,3))
[1] 4
> V(c(10,2,4,4))
[1] 6
> V(c(10,10,10,5,10))
[1] 5.8
> V(c(1,2,3,4,5,6))
[1] 11.15


Detecting events in time series data I am collecting data from a sensor over time, and I'm trying to figure out how to detect "events" in the data - specifically, when a given event begins and ends. The frequency, duration, and amplitude of these events varies.

Rather than using some rules-based scheme that proves to be rather ineffective, I want to train a model to detect these events for me. An example of my data (in only one dimension; I have multiple variables that I'm reading) looks like this:

There's one event here and some baseline data on either side.

My raw data before and during this event looks like:

1/1/2016 12:48:03   14.2
1/1/2016 12:48:04   12.8
1/1/2016 12:48:05   13.6
1/1/2016 12:48:06   13.5
1/1/2016 12:48:07   12.9
1/1/2016 12:48:08   15
...
1/1/2016 12:48:34   27.7
1/1/2016 12:48:35   30.3
1/1/2016 12:48:36   31
1/1/2016 12:48:37   32.8
1/1/2016 12:48:38   31.1
1/1/2016 12:48:39   28.7
1/1/2016 12:48:40   32.1
...

I have training data consisting of raw readings and timestamps that I can correlate to a truthset of event start and end times, but I don't know how I should go about featurizing to build a model. I assume I would keep a window of, say, 30 seconds or a minute of readings. (Events are typically more than a minute long, but I don't know whether I would need my window to contain the entire event.)

I'm familiar (but not an expert) with regression and boosted trees, and I know of tools that can generate code I can use without third-party libraries. But I don't know whether these are feasible approaches to solving my problem.

How can I go about detecting these events?

Edit: After some discussion, I've created the following graph to show what more data might look like from different signals. The duration of the manually labeled event is in blue (using the right axis labeled 0/1). Three signals show up strongly:

Red covers the overall event reasonably well and is essentially the above example
Purple-blue has an even stronger signal but only for the first half or so of the event
Yellow-green has a stronger signal than reed for maybe a third of the event, but basically after purple-blue dies off.

Some signals (eg, the bottom-most orange on the left side) have an increase during the event. These either have a weak signal that should be captured or have no signal; however, it's not obvious whether any correlations between these signals and events exist, and if so, how to extract them.

Your first step is to characterize what effect you expect an event to have on your signals.  Does it change the mean?  Increase the mean?  Change the variability?  The more you can say about the type of effect it will have, the more specific a test you'll be able to build, and thus the more effective any analysis is likely to be.

Then, your second step is to apply appropriate techniques from the statistics literature on time series analysis.  There are many techniques that look applicable here:

You could look for change points, where the mean value changes.  For instance, the CUSUM procedure might be useful.  Look into the theory on change point detection; there's lots of work on it.  See also https://stats.stackexchange.com/questions/tagged/change-point.
You might also find literature that describes this as looking for a level shift in time series data.  It's basically the same thing.
You might be looking for a "structural change" in the signal, which is a bit more broad/general than change point analysis.  See, e.g., https://stats.stackexchange.com/questions/tagged/structural-change.

I recommend you start with some exploratory analysis.  Based on the underlying physics/mechanics of how your system works, try to identify some ways that an event might affect the resulting signals.  Also, do some exploratory data analysis: find some examples of known events, visualize the signals during those time periods, and hypothesize some feature values that seem to be affected during the signal (e.g., the mean got larger; the standard deviation got larger; the mean of the absolute value of the first derivative got larger; something like that).  Finally, look for appropriate techniques in the statistical literature.  If you can characterize the effect of an event well, you might be able to use change point detection techniques that will work well.  If you can't characterize the effect of an event, you might need to fall back to some kind of machine learning, trained using a large training set... but you should still do each of the steps I listed, to help you identify what features might be useful to use in your machine learning model.


Algorithms which are both deterministic and non-deterministic I'm just starting my second year in computer science and one of my classes briefly touched upon deterministic vs. non-deterministic algorithms. This got me thinking - is there any use for algorithms which return deterministic output for certain inputs, but non-deterministic output for other inputs? Say, something along the lines of

$$
s\leftarrow n\in\mathbb{R}\\
\text{if }s\le 5:\text{ return }2\times s\\
\text{else }x\leftarrow\text{generateRandomNumber()};\text{ return }s\times x
$$

This algorithm returns the input, doubled, if the input is less than or equal to five, and otherwise returns it multiplied by a random number (assuming the RNG returns a truly random number and is itself non-deterministic).

So once again, my main question: are algorithms of this nature useful in any practical application? Additionally, what would this class of algorithm be called? Semi-deterministic? Pseudo-deterministic?

First of all, your terminology is at odds with computability and complexity theory. What you are asking is whether it makes sense for an algorithm to have both randomized and non-randomized components. A good example are algorithms which have to be unpredictable (say for cryptographic reasons), but for the purpose of testing have to be predictable. In this case, we substitute a pseudorandom number generator for the true (say, physical) random number generator for testing purposes.

That said, the class of algorithms you are describing are just randomized algorithms. Nothing forces a randomized algorithm to use randomization, it's just a possibility in the model, in the same way that a non-deterministic Turing machine can be deterministic, or that a real number can be rational.


predicate logic proof of 2 numbers For any two different numbers there is an number in between.

I'm trying to write this in predicate logic and have no idea how to do it, since I need 2 variables X and Y?  For all x there exists a y such that y - x is positive?

I'm a mong ignore.

As a hint, for any two numbers there is a third number in between.


Wouldn't a Red-Black tree fix up after insertion mess up the BST ordering? I've been reading about fixing up after an insertion into a red black tree. (http://web.cse.ohio-state.edu/~lai/2331/0.Red-Black%20Trees.pdf)

The most surprising part is not that there are 6 things that we need to do after inserting into a red black tree. i.e. if both parent, uncle red, then parent, uncle black, grandparents red, replace inserted value with grandparent. The most surprising part is that wouldn't this blatantly mess up the BST ordering such that a node x is always greater than the left side and less than the right side?

In above link, page 10, the author just replaced grandparent with the newly inserted node x. Wouldn't this completely mess up the BST ordering? Can someone explain if BST ordering should be preserved in a red-black tree and why rotation/fix up after insertion will not have any affect on this ordering?

A correct implementation of red-black trees will maintain the BST ordering property. Whenever you add a node to the tree or delete a node from the tree you very carefully maintain this property. If you have to modify the structure of the tree then you do so in such a way that maintains the BST property.

I suggest you go carefully through the insertion and deletion pseudocode and verify that both operations maintain the BST property.


Proving a language comprised of 2 languages is regular(with suffix and prefix) I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular:

$$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\sigma_n\mu_nv\}$$

$u,v \in \Sigma^*$
$0\leq n$, for every i($1\leq i \leq n$): $\sigma_i,\mu_i \in \Sigma$
$\sigma_1...\sigma_n \in L_1$
$\mu_1...\mu_n \in L_2$

I don't understand how to prove if because of the suffix and prefix(u,v accordingly).

If it weren't for u,v what I think I would've done is building an automaton(Deterministic finite automaton): $A=\left(Σ,Q1xQ2x\left\{1,2\right\},\left(q01,q02,2\right),F1xF2x2,δ\right)$, Ending in accepting iff both automatons that accept each language end in an accepting state, and $L_2$ needs to be after $L_1$ from the language's description. However, I don't know how to deal with the u,v in the beginning and in the end. I am not sure how to configure it correctly to prove $L^\frown$ is regular.

Would very much appreciate your assistance with it.

Your language is the concatenation $\Sigma^* L \Sigma^*$, where $L$ is the so-called perfect shuffle of $L_1$ and $L_2$. There are at least two proofs that the perfect shuffle of two regular languages is regular on this site: using automata and using closure operations.

If you are hell-bent on constructing an automaton for $\Sigma^* L \Sigma^*$, start with one for $L$, then follow the automata proof of closure under concatenation (which constructs an NFA).


Does inserting and immediately removing a node change a red-black tree? I have the following problem:

  Does inserting a node into a red-black tree and then immediately deleting it always result in the original tree? Prove that it does or give a counter-example if it does not. Does deleting a leaf node from a red-black tree, then reinserting the same node always result in the original tree? Prove that it does or give a counter-example if it does not.

I have used several demos, but none of them have made much sense to answer this question. I havent been sure as to yes or no, I am still new to binary trees.

It's not obvious that there is a "correct" answer to this question, as there are multiple insertion/deletion algorithms for red-black trees. Tarjan explicitly explains this in his book Data Structures and Network Algorithms, where he demonstrates (in section 4.2) update algorithms that require $O(1)$ rotations and references algorithms that require $\Omega(\lg n)$ rotations.

This is also mentioned in Hize's "A Simple Implementation Technique for
Priority Search Queues" and Driscoll et al.'s "Making Data Structures Persistent"


Converting a algorithm to a runtime function I need to find an upper limit for the runtime of $f(n)$.

f(n):
{
 g(n,1)
}

g(n,k):
{
 if n<=0 return;
 for(i=1; i<=n; i++)
 {
  print "I love data structures!";
  k++;
  g(n-1, k);
 }
 return;
}

I tried to think of it this way:

for(i=1; i<=n; i++) $\rightarrow (n+1)c_2$

g(n-1, k) $\rightarrow ng(n-1)$

$$f(n) = g(n,1) + c_f = c_1 + (n+1)c_2 + nc_3 + nc_4 + ng(n-1) + c_f$$

I am not sure about the recursion runtime analysis:

g(n-1,k) $\rightarrow ng(n-1)$

Thank you!

The recursion for $g$'s running time is $$T(n)=n(T(n-1)+1)$$ where $1$ is the (constant) work done from the print statement and incrementing $k$. $g(n-1,k)$ and the constant work are called $n$ times from the for loop.
The recursion stops at $g(0,k)$ which has running time $T(0)=1$.

Solving this recursion on Mathematica (I suspect doing it by hand would involve induction or inspection) gave the result:
$$T(n)=\Gamma(n+1)+en\Gamma(n,1)$$
The complexity of this is
$$T(n)=O(\Gamma(n+1)+en\Gamma(n,1))$$
$$T(n)=O(n\Gamma(n,1))$$
Since $n$ is an integer, then we can reduce this to
$$T(n)=O(n!)$$


Minimum number of moves in this Graph Coloring "Game" You're given a graph $G = (V, E)$ and a set of colors $C = \{c_1, \cdots, c_v\}$, and the task is as follows:

Color the vertices using the colors in $C$.
Remove any edges that have differing colors for its endpoints (of course, if a vertex eventually has all edges removed, it can be deleted - but it is not necessary).
Repeat the above two steps until there are no edges left in the graph.

Suppose that $k = |V|$ is the number of vertices, $m = |E|$ is the number of edges, and $v = |C|$ is the number of colors. I am interested in the quantity $p(k, m, v)$, which is the smallest number of iterations of the above algorithm given $k, m, v$. Of course, we need $v \ge 2$ (couldn't remove any edges otherwise), and $p(k, m, v) \le m$ because we can color one edge at a time. We can also denote this quantity by $p(G, v)$.

Based on a combinatorial object that is equivalent with respect to this procedure (perfect hash families), when we have the complete graph $K_k$, one can prove that $p(K_k, v) = \lceil \log_v(k) \rceil$. So of course $p(k, m, v) \le \lceil \log_v(k) \rceil$ if $G$ is a simple graph.

But the more interesting case is when we have $G$ be a hypergraph. Here, we remove hyperedges that are rainbow (i.e., every vertex in the hyperedge is a distinct color). Based on PHFs, there are lower and upper bounds for $p(G, v)$ when $G$ is the complete $t$-uniform hypergraph. In general, $p(G, v) \in \Theta(\log k)$ for these graphs, but the hidden constant heavily depends on $v, t$.

Are there references that have looked at a similar problem for hypergraphs?

The value of $p(G,v)$ is at most $r$ if you can label the vertices of $G$ with colors from $[v]^r$ in such a way that the colors assigned to every pair of adjacent vertices differ on at least one coordinate. Equivalently, $p(G,v) \leq r$ if you can label the vertices of $G$ with colors from $[v]^r$ in such a way that every pair of adjacent vertices gets a different color. Stated differently, $p(G,v) \leq r$ iff $\chi(G) \leq v^r$, where $\chi(G)$ is the chromatic number of $G$. This implies the formula
$$ p(G,v) = \lceil \log_v \chi(G) \rceil. $$
A similar relation should hold for the case of hypergraphs if you use the correct definition of chromatic number.


What are the examples of problems which first had large polynomial time complexity algorithms but later the complexity was reduced significantly? Arora-Barak says

  It has also happened a few times that the first polynomial-time
  algorithm for a problem had high complexity, say $n^{20}$, but soon
  somebody simplified it to say an $n^5$ time algorithm

What are some examples of the above statement? I know AKS is one, are there any other?

Approximating volume of convex bodies

In Dyer et al.: A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM) 38.1 (1991): 1-17.
a $O(n^{19})$ approximation algorithm was proposed.

The work of Lovász et al.: Simulated annealing in convex bodies and an $O^*(n^4)$ volume algorithm. Journal of Computer and System Sciences 72.2 (2006): 392-417. proposed an $O^*(n^4)$ algorithm, where the asterisk denotes that the dependence on error parameters and on logarithmic factors in $n$ is not shown (according to their paper).

Maybe you may find this thread useful: https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant/


Get the running time of forest disjoint sets If you have a forest implementation of disjoint sets, and have the union by weight/rank heuristic where you append the smaller one. Then why is the worst case running time Θ(m log n)? (m is the number of disjoint sets and n is the number of Make Set operations.)

You've asked two questions:

Why is the tree height Θ(log n)?
Why is the runtime Θ(m log n)?

This answer addresses both questions.  I'll start off with a review of the ranks of the different trees to go over some basics, then discuss these time bounds.

One trick that might be useful here is to think of the minimum number of nodes that can be
in a tree of height n.  Once we have that insight, we can try to relate the maximum runtime to the maximum height of any tree in the forest.

When we initially create all of the trees, they each have height 0 and have a total of 1 node in them.  Now, suppose we want to create a tree of height 1.  The only way to do that would be to merge together two trees of height 0 to form a new tree of height 1.  This would have a total of 2 nodes in it, and that's the minimum number of nodes possible.

Next, suppose we want to create a tree of height 2.  To do that, we have to merge together two trees of height 1.  Each of those trees has a minimum of 2 nodes in them, so the minimum number of nodes possible in a tree of height 2 would be 4.

To make a tree of height 3, we need to merge two trees of height 2, each of which has at least 4 nodes.  This means that we would end up with eight nodes in the tree.

If we look so far, we see this pattern:

Height 0: At least 1 node.
Height 1: At least 2 nodes.
Height 2: At least 4 nodes.
Height 3: At least 8 nodes.

It looks like a tree of height n will have at least 2n nodes in it.  This makes intuitive sense - the only way to make a tree of height n + 1 is to merge together two trees of height n, so the minimum number of nodes in a tree of height n + 1 should be at least double the number of nodes in a tree of height n.

So now let's suppose we do a series of n different union operations to link trees together.  What is the largest possible tree we can make?

Suppose that we want to make a tree of height k.  In order to do that, we first need to make two trees of height k - 1.  Each of those trees are formed from two trees of height k - 2 each, and those trees are formed from two trees of height k - 3 each, etc.  Eventually, we bottom out at trees of height 0.

If we work out a recurrence relation, we get the following expression for the total number of union operations required to get at tree of height k:

U(0) = 0
U(k + 1) = 2U(k) + 1

If we expand out the terms in this recurrence, we get

U(0) = 0
U(1) = 1
U(2) = 3
U(3) = 7
U(4) = 15
...
U(k) = 2k - 1

In other words, if we want to get to a tree of height k, we need to do 2k - 1 link operations.  This means that if we do a total of n union operations, the maximum tree height we can possibly make has height Θ(log n).

This explains the runtime bound you were curious about.  Creating the disjoint set forest takes time O(m), where m is the number of elements.  Each union operation requires us to walk up to the root of a tree whose height is at most Θ(log n), so if we do a total of n of these, the overall runtime is at worst Θ(m + n log n).

Note that this is different from the bound you've proposed.  However, if you make the assumption that m = Θ(n) (that is, you do about the same number of union operations as there are nodes in the graph), then we get that Θ(m + n log n) = Θ(n + n log n) = Θ(n log n) = Θ(m log n), which matches the bound you've described.

Hope this helps!


Resolution and what it means to derive the empty set When using resolution, if the empty set {Ø} is derived from a formula like {¬x,¬y} {x,y}, does that mean the formula is unsatisfiable?

If this is the case, why is {x,y},{¬x,¬y},{x,¬y} satisfiable, and

{x},{¬x},{x,y,z,w} is not satisfiable?

To complete the Kyle's answer:

A CNF (in Conjunctive normal form) formula, $F$, can be considered as a set of clauses, eg : $F=\{C_1,C_2 \ldots C_m\}$ and each clause can be regarded as a set of literals, eg : $C_1=\{x,y\}, C_2=\{\lnot x, \lnot y\}$.

If $F=\varnothing$ i.e. $F$ is the empty set and does not contain any clause then $F$ is satisfiable (=tautology).

If $F=\{\varnothing, C_1 \ldots\}$ i.e. $F$ contains the empty clause then $F$ is not satisfiable. The empty clause can be obtained by the resolution rule eg : the resolvent of $C_3=\{x\}$ and $C_4=\{\lnot x\}$ is the empty clause $\varnothing=\{\}$.


Why would total comparison of functions solve the Halting problem? Why would total comparison of procedures solve the Halting problem?

I've read that if all procedures could be represented syntactical e.g. in Scheme, then they could be compared structurally using the predicate =, and this would in turn solve the Halting problem.

Having read the ordinary proof why the Halting problem cannot be solved by any Turing machine (by reaching a contradition if such algorithm exists), I still cannot see why the comparison of functions would imply the contrary.

The specific representation of functions doesn't really matter here, so we'll talk about the usual encoding of Turing machines. We denote the encoding of a machine $M$ by $\langle M \rangle$ (if this bothers you, think of it as the scheme code of the function).

Nothing prevents you from comparing two machines syntactically (by comparing the encoding/scheme code as strings). The problem arises when you claim that you have an operator "$=$" which checks whether the functions are equivalent semantically, i.e. give the same result for each input.
In the language of Turing machines, this means you can decide the following language:

$L = \left\{\left(\langle M_1\rangle ,\langle M_2 \rangle \right) | L(M_1) = L(M_2)\right\}$

The halting problem can be reduced to the above. Given $\langle M\rangle$ and $w\in \Sigma^*$, ask whether the machine $M_w$ which disregards the input, simulates $M$ on $w$, and accepts, computes the constant $1$ function. Thus, $L$ is not decidable. In fact, it is $\Pi_2^0$ complete, so $L$ is not even semi decidable.


How do I "tell" a simple perceptron/adaline neural netrork its output can't be negative? I have made and trained a simple neural network which now seems to produce outputs reasonable  in all the aspects but one: it gives negative values from time to time even though the outputs are always either 0 or 1 (positive) in all my treaining samples (the actual neural outputs show to be more or less close to the answer most probable but never actually reach them, I consider this ok). Won't "telling" the network what output values are just impossible improve its performance.

Perhaps my mistake is in choosing activation functions. As far as my input values domain is (-1, 1) I use TANH for input neurons, but I have no idea what is the logic to choose hidden and output neurons activation functions and so I set the same (TANH) for all of them (update: I have just noticed that I have mistakenly chosen linear activation function for the output layer while inpit and hidden layers use TANH).

Clearly a negative value means "the answer is very probable to be zero" in this case and it works just fine from the practical point of view but it still gives me a sense that I am doing something wrong.

You can put the logistic function on top of the output:

f(z) = 1/(1 + exp(-z)).

You will also need to adjust the cost function accordingly, i.e. use log loss: https://www.kaggle.com/wiki/LogarithmicLoss


Is there a difference between top-down and bottom-up dynamic programming? Is there a fundamental difference between top-down and bottom-up dynamic programming?

In particular, is there a problem which can be solved bottom-up but not top-down? Or is the bottom-up approach just an unwinding of the recurrence in the top-down approach?

To use the bottom up method you need to be able to efficiently determine what the "bottom" is, which usually means you need a heavily constrained problem space.  If you know what the lowest level calculations are going to be and the dependency order going upward, it makes sense to iteratively do them in the proper order and store those results.  Factorials, naive Fibonacci and the Euler recurrence relation for partitions are all good examples of problems suited to this approach.

Some problems don't have an easily determined bottom or dependency order for the calculations.  Chess positions evaluations, for example, are usefully memoized by position, with the evaluation score stored so it need not be recalculated.  Positions can recur at multiple levels of the search tree due to move transposition and repetition so saving evaluation results is worthwhile.  But there's no way to know what the positions at the lowest levels of the tree are going to be without recursively descending (and taking into account intermediate pruning) so top down is really the only feasible approach.


Residual Graph in Maximum Flow I am reading about the Maximum Flow Problem here. I could not understand the intuition behind the Residual Graph. Why are we considering back edges while calculating the flow?

Can anyone help me understand the concept of Residual Graph?

How does the Algorithm change in Undirected Graphs?

The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture. The explanation goes as follows.

Suppose that we are trying to solve the maximum flow problem for the following network $G$ (where each label $f_e/c_e$ denotes both the flow $f_e$ pushed through an edge $e$ and the capacity $c_e$ of this edge):

One possible greedy approach is the following:

Pick an arbitrary augmenting path $P$ that goes from the source vertex $s$ to the sink vertex $t$ such that $\forall e \: (e \in P \rightarrow  f_e \lt c_e $); that is, all of the edges in $P$ have available capacity.
Push the maximum possible flow $\Delta$ through this path. The value of $\Delta$ is determined by the bottleneck of $P$; that is, the edge with minimum available capacity. Formally, $\Delta=\min_{e \in P} (c_e-f_e)$.
Go to step 1 until no augmenting paths exist.

That is, find a path with available capacity, send flow along that path, and repeat.

In $G$, one possible execution of the above heuristic finds three augmenting paths $P_1$, $P_2$, and $P_3$, in this order. These paths push 2, 2, and 1 units of flow, respectively, for a total flow of 5:

Choosing paths in this order leads to an optimal solution; however, what happens if we select $P_3$ first (i.e., before $P_1$ and $P_2$)?

We get what is called a blocking flow: no more augmenting paths exist. In this case, the total flow is 3, which is not optimal. This issue can be resolved by allowing undo operations (i.e., by allowing flow to be sent in reverse, undoing work of previous iterations): simply push 2 units of flow backwards from vertex $w$ to vertex $v$ like this:

Encoding these allowed undo operations is the main goal of the residual graph.

A residual graph $R$ of a network $G$ has the same set of vertices as $G$ and includes, for each edge $e=(u,v) \in G$:

A forward edge $e'=(u,v)$ with capacity $c_e-f_e$, if $c_e-f_e \gt 0$.
A backward edge $e''=(v,u)$ with capacity $f_e$, if $f_e \gt 0$.

For example, consider the residual graph $R$ that is obtained after the first iteration of the greedy heuristic when the heuristic selects $P_3$ first (that is, when it gets the blocking flow):

Note that the undo operation that pushes 2 units of flow from $w$ to $v$ is encoded as a forward (augmenting) path from $s$ to $t$ in $R$:

In general:

  When an augmenting path $P'$ is selected in the residual graph $R$:

  Every edge in $P'$ that corresponds to a forward edge in $G$ increases the flow by using an edge with available capacity.
  Every edge in $P'$ that corresponds to an edge going backwards in $G$ undoes flow that was pushed in the forward direction in the past.

This is the main idea behind the Ford–Fulkerson method.

The Ford–Fulkerson method proceeds in exactly the same way as the greedy approach described above, but it only stops when there are no more augmenting paths in the residual graph (not in the original network). The method is correct (i.e., it always computes a maximum flow) because the residual graph establishes the following optimality condition:

  Given a network $G$, a flow $f$ is maximum in $G$ if there is no $s-t$ path in the residual graph.


Why postfix is used more often than prefix expression? i was reading stack and i came across the infix, preifx and postfix expression.So i understood that why postfix /prefix expressions are preferred over infix expression ( due to its unambiguous nature) .But i am not getting any enough information  about the popularity reason of postifx expression over prefix expression.

Why are we not using prefix expression than the postfix expression more often?

I am guessing that ,

it's related to the easiness of converting the infix to postfix
or the evaulation process of postifx is easy than prefix.

If so, Please someone elaborate on it.

thanks.

The evaluation is easier for postfix-notation expressions.
The evaluation is done easily using a stack. The expression is processed from left to right, one token at a time:

operand -> put it on the stack;
operator -> get from the stack the number of values it needs (two for +, three for ?:, one for unary - and so on), combine the values using the operator and put the result on the stack.
when the entire expression is processed, the stack contains only one value; it is the value of the entire expression.

The prefix-notation expressions can be evaluated using a similar algorithm that uses the operands (instead of the operators) to trigger computations. However, it is not that straight-forward; it involves lookups on the top of the stack to find the operator and to decide if enough operands were read for it.
The prefix-notation expressions can also be evaluated from right to left using the same algorithm as for postfix-notation expressions.


Why multiplying float number by multiple of 10 seems to preserve better precision? It is famous that for float numbers:

.1 + .2 != .3

but

1+2=3

It seems that multiplying floats by 10 allows you to preserve more precision. To further illustrate the case, we can do this in python:

sum([3000000000.001]*300)
#900000000000.2957

sum([3000000000.001 * 1000]*300) / 1000
#900000000000.3

By multiplying each element in the list by 1000 and divide the sum of the list by 1000, I can get the "correct" answer.
I am wondering:
1) why it's the case.
2) Will this always work, and
3) At what magnitude, will this method backfire, if it will.

The only numbers that can be stored exactly are rational numbers whose denominator is a power of 2 (read any source on floating point numbers to understand why). For example, floating point numbers do satisfy
$$ 1/4 + 2/4 = 3/4 $$
but do not satisfy (or rather, don't necessarily satisfy)
$$ 1/3 + 2/3 = 3/3. $$
There's nothing magical about the number 10. It's just an artifact of the common decimal representation. So in general it won't help to multiply by a power of 10.


A property of Kolmogorov random strings I am working on the following problem:

Prove that, for all $k\in\mathbb N$, there exists $n\in\mathbb N$ so that every binary string $x\in\{0,1\}^{kn}$ with Kolmogorov complexity $K(x)$ at least $kn$ satisfies the following property:
By interpreting $x$ as $x_1\cdots x_n$, with $|x_i|=k$, for any $z\in\{0,1\}^k$ there is an index $i$ for which $x_i=z$.

To show this, I want to suppose that if there exists a string $x$ of length $kn$ so that, after writing $x=x_1\cdots x_n$, not all $k$-bit binary strings appear in $x_1\cdots x_n$. Then ideally I want to show that $x$ can be described in less than $kn$ bits, which means $x$ have Kolmogorov complexity less than $kn$, which establishes the contradiction I want.
Any hints on how to do this?
For completeness, the Kolmogorov complexity of a string $x$ is defined as the length of the shortest description of $x$. And by the description of a string $x$, I refer to a pair $(M,w)$, where $M$ is a Turing Machine and $w$ is some string, so that $M$ halts on $w$ as input, leaving behind $x$ on the tape. I encode the pair $(M,w)$ as $0^{|M|}1Mw$. Then, for any string $x$, if $M$ is a Turing Machine that halts immediately upon execution, then $(M,x)$ is a description for $x$, of length $2|M|+|x|+1$. Hence the Kolmogorov complexity of $x$ does not exceed $2|M|+|x|+1$.

Suppose that $x = x_1 \cdots x_n$, where $|x_i| = k$, and there exists some $z \in \{0,1\}^k$ such that $x_i \neq z$ for all $i$. We can encode $x$ by first listing $z$, and then encoding each $x_i$ using $\log_2 (2^k-1)$ fractional bits. The program also needs to know $n$. This shows that
$$
K(x) \leq \log_2 (2^k-1) \cdot n + C_k + O(\log n),
$$
where $C_k$ is a constant that depends only on $k$. In particular, if $n$ is large enough that the upper bound will be less than $nk$.


How to draw (intuitively) the first and second principal component in PCA methods? Assume I have some data in 2D. How to draw the first and second principal component in PCA method?

By referring to the image: the plot on the right is confusing, how I can detect the position of first PCA?

In the case of 2d data, the first principal component will be aligned along the direction of major continuity, and the second will be perpendicular to that, aligned along the least continuous direction. Generally just the eigen vectors at the mean x / mean y.

Sort of like so (sorry for the poor drawing)

My favorite reference on pca is A TUTORIAL ON PRINCIPAL COMPONENT ANALYSIS by Jon Shlens: pdf His example is in figure 2.

To address your comment:


trouble with bijection definition I have a bijection problem that I cannot get my head around. It goes like this:

let f: A -> B and g: B -> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g must be onto. And also an example showing that it is possible for neither f nor g to be a bijection.

This is the problem. I do not even know where to begin. Any help is appreciated.

Hints: First part: Suppose that $f$ is not one-to-one. That implies that $f(x) = f(y)$ for some $x \neq y$. Can $g \circ f$ be a bijection? Similar idea for the other half. Second part: We know that $f$ must be one-to-one and $g$ must be onto. So if $f$ and $g$ are not bijections, then $f$ must not be onto and $g$ must not be one-to-one. See how these two conditions mesh together.


Are there BBP formulas for all computable numbers? A BBP algorithm is a formula with the following form where $b \in \mathbb Z$, $b \ge 2$, and $p(k)$ and $q(k)$ are polynomials in $k$
$$\sum_{k=0}^{\infty}\frac{1}{b^k}\frac{p(k)}{q(k)}$$
There are known BBP formulas for many computable numbers and it is easy to prove that any number with a BBP formula is computable.

Obviously all rationals have BBP formulas, let $n$ equal the length of the period in base $b$ and let $q(k)=1$ and $p(k) = \lfloor b^n\frac{p}{q}\rfloor$

I don't believe that there is a general form like that for all computable reals, i.e. you cannot given a definition of an irrational $\alpha$ derive $b$,$p(k)$,$q(k)$, but is it true that one exists for all computable numbers?

You can easily use diagonalization to construct a computable real which is not of this form. Fix some enumeration of all triplets $(b,p,q)$. I will describe a process that generates binary digits of a real number.

The process goes over all triplets $(b,p,q)$ in the fixed order. Suppose that it's time to handle $(b_i,p_i,q_i)$, and that currently we have generated the digits $\beta_1 \dots \beta_n$. The process evaluates the corresponding sum $S(b,p,q)$ to such a precision that the first $n+1$ binary digits can be gleaned for it. It outputs $\beta_{n+1}$ so as not to equal to $S(b,p,q)$.

The argument as stated is not 100% correct, and I'm leaving it to the reader to discover where I cheated and to fix the proof.


Why does a DFA have multiple final states? I am taking a course on programming language design and we got to the DFA part. It is known to be formally defined by a 5-tupple but they did not make it very clear to us why a DFA can have multiple final states. I know that the languages that it can accept are involved, but nothing else.

A DFA is a machine that reads in its input left to right, and, while reading, keeps track of its internal state. At the end, it has to decide whether to "accept" or "reject" the input based only on whatever internal state it has at the end. The final states are used to indicate which internal states should inform the machine to accept.

The reason we need to have multiple final states, then, is because we might want to accept the input in multiple different scenarios. Here is a simple example. Suppose we want to design a machine that accepts if the input is either ho, hoho, or hohoho (so we want to accept, in total, three possible input strings). Then the "state" of the machine can keep track of what letters we have seen so far: we have 7 states for [nothing], h, ho, hoh, hoho, hohoh, hohoho. If we get a letter that isn't going to be one of these strings (like if the input is haha or asdf), we need a different state to remember that the input was bad, and we can call that state [bad input]. So in total we have 8 states.

Now in this example, we want to accept three different strings: ho, hoho, and hohoho, so we need all three of those states to be final. It turns out that it would be impossible to accept these three strings if we have to have only one final state.

All states (8): [nothing], h, ho, hoh, hoho, hohoh, hohoho, [bad input]
Final states (3): ho, hoho, hohoho

In summary, multiple final states gives us the ability to accept multiple different possible patterns in the input. The above is one example of that, but there are many other examples where it is useful.


Time complexity of the travelling salesman problem (Recursive formulation) According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (neighbor vector is the same set and v is cost matrix):
recursion formula :
C(i,S) = min { d(i,j) + C(j,S-{j}) }

my code :
#include <iostream>
#include <vector>
#define INF 99999
using namespace std;
vector<vector<int>> v{ { 0, 4, 1, 3 },{ 4, 0, 2, 1 },{ 1, 2, 0, 5 },{ 3, 1, 5, 0 } };
vector<int> erase(vector<int> v, int j)
{
    v.erase(v.begin() + j);
    vector<int> vv = v;
    return vv;
}
int TSP(vector<int> neighbor, int index)
{
    if (neighbor.size() == 0)
        return v[index][0];
    int min = INF;
    for (int j = 0; j < neighbor.size(); j++)
    {
        int cost = v[index][neighbor[j]] + TSP(erase(neighbor, j), neighbor[j]);
        if (cost < min)
            min = cost;
    }
    return min;
}
int main()
{
    vector<int> neighbor{ 1, 2, 3 };
    cout << TSP(neighbor, 0) << endl;
    return 0;
}

In fact, the erase function removes the element j from the set (which is the neighbor vector)
I know about dynamic programming that prevents duplicate calculations (like the Fibonacci function) but it does not have duplicate calculations because if we draw the tree of this function we see that the arguments of function (i.e. S and i in formula and like the picture below) are never the same and there is no duplicate calculation.
My question is, is this time O(n!)?
picture :
If yes,why? This function is exactly the same as the formula and it does exactly the same thing. Where is the problem? Is it doing duplicate calculations?

The full recursion tree for your problem has as root $(1,\{2,\ldots,n\})$. The children of a node $(i,S)$ are $(j,S \setminus \{j\})$, where $j$ ranges over all elements of $j$. Nodes with $S = \emptyset$ have no children.
Let us annotate each node in the tree by its "history". Instead of annotating each node by an index and a set, we annotate it with a sequence and a set. The root is $(1;\{2,\ldots,n\})$. The children of a node $(a;S)$ are $(a,j;S \setminus \{j\})$ for all $j \in S$. For example, if $n = 3$ then the nodes are:

$(1;\{2,3\})$.
$(1,2;\{3\})$.
$(1,3;\{2\})$.
$(1,2,3;\emptyset)$.
$(1,3,2;\emptyset)$.

A node $(a_1,\ldots,a_m;S)$ in the new tree corresponds to the node $(a_m,S)$ in the original tree. Conversely, each node $(a,S)$ corresponds to nodes $(1,a_2,\ldots,a_{m-1},a;S)$, where $m = n - |S|$ and $\{1,a_2,\ldots,a_{m-1},a\} = \overline{S}$. There are $(n-2-|S|)!$ ways to choose $a_2,\ldots,a_{m-1}$, and so the node $(a,S)$ appears $(n-2-|S|)!$ times in the original tree.
This shows that the full recursion tree for your problem does contain duplicates.


find total components in a graph I have a graph with N nodes and M edges. It is a single component.

Now I have to delete a single node from graph, deleting that node might split graph into 1,2 or more components. The count of such components is required for each deleted node. Note that only a single node is deleted at any point of time.

I need to do this for all the nodes of the graph in a linear time.

Is this possible in linear time? I am able to do this in O(n^2) by running dfs for each node.

Yes, this can be done in linear time. The vertices whose removal causes the graph to split into multiple components are called articulation points. The number of such components for each vertex is the number of biconnected components that the vertex belongs to. For biconnected components and algorithms for computing them see the wikipedia page https://en.wikipedia.org/wiki/Biconnected_component.


How to encode reachability in a graph with walls as a SAT problem Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we may only move to adjacent cells (diagonal movements are not allowed).

My question is how would one encode this problem in CNF to be solved by a SAT solver?

For example, let the graph represent the following 2 x 3 grid:

0 1 0
0 0 0

where 0-cells are cells we may be in or move to and 1-cells are walls. Suppose we start in (0, 0) and want to move to (0, 2). Then there is a path.

On the contrary, consider another 2 x 3 grid with the same start and destination positions:

0 1 0
0 1 0

Then this graph does not have a path from start to destination.

Clearly we may run BFS on the graph and if there's a path we can encode it as a trivially satisfiable CNF, or if there isn't then encode it as a trivially unsatisfiable CNF. For example, $A$, or, $A \land \neg A$.  However, the point of my exercise is to encode the path existence in CNF.

This is indeed part of my homework. I have been stuck for a while now. Some help on this problem would be greatly appreciated.

The point of my exercise is to encode the path existence in CNF

Well, a trivial way to do this is by reducing the problem to 2-SAT, following this set of rules:

Assing a literal to every edge of your graph, for example first element in first row become $a$, second element in first row become $b$ etc.
Put in OR relation the literal in the "start" position with each adjacent literal (
thus obtaining the clauses of your formula). If one or more adjacent literal has value 1, omit the clause in which it appears. Note that, when they are both 0, you dont need to repeat them:
if you have an adjacency between $a$ and $b$, you do not have to repeat the clause between $b$ and $a$.Furthermore you must not consider the diagonal adjacencies.
Perform the same procedure for all the literals adjacent to the starting one and for those in turn, until you reach the destination literal.
Connects all the obtained clauses  with an AND

To better adapt to your example, in which a 0 value means "you can pass" and a 1 value means "you cannot pass", you can negate all the literals in the formula.

So for the  matrix in the first above example  the corresponding path existence encoded into 2-SAT instance will be:

$(\not a \lor\not d) \land (\not d \lor\not e) \land (\not e \lor\not f) \land (\not f \lor\not c)$

By replacing the matrix values in the first example, the formula evaluates to 1, which means that this formula encodes a valid path.
However, for the secon matrix in the example, you never obtain a true formula in which the ending literal is present, so there is no valid path.


Find a repeated element in linear time Given an array of $n$ elements, containing values in the range $[1, n-1] $ (assume $ n > 1 $) this implies there is at least one repeated element. The problem is to get one of the repeated values in linear time on average.
My first try was to do something with the Partition scheme from Quicksort. However, I don't know how to address the following problem:

We can divide the problem selecting a pivot, and then for each value $ <= $ than the pivot, we know that they will be in the range $0..n/2 - 1$, and the following values $>$ than the pivot, they will be in $n/2 + 1..n$.

I can't check both of those partitions, because the cost would be $O(n\log n)$ per Master Theorem.
The only way I think I can do it is only checking left or right, however, i.e., if the repeated element was in the left and I check the right, is going to be somewhat the same.
So my intuition is telling me that maybe, if I check first the left part for this condition, and after that, the right one in some recursive manner, this is going to give me a linear algorithm on average.
Am I right or is there any better way to do it?
Edit: the divide and conquer approach is mandatory

If you choose $\frac{n}{2}$ as the pivot to do the partition, you just need then to continue the search in the half containing strictly more than $\frac{n}{2}$ elements.
That way you don't have to check both halves.


Reduce $SAT$ to $3SAT$ I was reading this that details a polynomial reduction from $SAT$ to $3SAT$.

In case $k = 1$ or $k = 2$, why don't we just replace those clauses with $C_i' = \{{z_1, y_{i, 1}, y_{i, 2}}\}$ and $C_i' = \{{z_1, z_2, y_{i, 1}}\}$  respectively? Instead, it suggested to replace them by $C_i' = \{(z_1, y_{i, 1}, y_{i, 2}), (z_1, y_{i, 1}, \overline{y_{i, 2}}), (z_1, \overline{y_{i, 1}}, y_{i, 2}), (z_1, \overline{y_{i, 1}}, \overline{y_{i, 2}})\}$ and $C_i' = \{(z_1, z_2, y_{i, 1}), (z_1, z_2, \overline{y_{i, 1}})\}$ respectively.

Let's take the case $k = 1$. Consider the CNF $z_1 \land \lnot z_1$. You suggest replacing it by
$$
(z_1 \lor y_{1,1} \lor y_{1,2}) \land (\lnot z_1 \lor y_{2,1} \lor y_{2,2}).
$$
Hopefully you see the problem now.


How to prove $L \notin \texttt{DSPACE}(f)$ I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to prove:

$$
L \notin \texttt{DSPACE}(f(n))
$$

How would I do this?

My first attempt was to reduce a language $L'$ from $\texttt{DSPACE}$ to the language $L$, but I don't know of any language in $\texttt{DSPACE}$ and I don't know if I can "simply" reduce it. Does anyone have a reduction that I see and try to understand?

The exact exercise specifies the language $L$: it is $\{ w\mid w \in T(M_w),M_w \text{ needs space |w|}\}$.

Also, we are given that $f(n) \in \Omega(\log{n})$.

Unfortunately, when you tried to ask a general question to get hints for your homework exercise rather than the solution, you turned the question into something too general to answer. I'll try to come back at some point and write something more useful, now that you've made the question more specific. Diagonalization is the usual technique, similar to how the halting problem is proven undecidable.

You're not going to prove that a completely generic language $L$ is not in $\mathrm{DSPACE}(f(n))$ for a completely generic function $f$.  Any such proof is going to have to rely on some properties of $L$ and $f$: quite apart from anything else, if you fix a decidable language $L$, then there are infinitely many functions $f$ such that $L$ is in $\mathrm{DSPACE}(f)$ and, conversely, if you fix any "reasonable" function $f$, there are infinitely many languages in $\mathrm{DSPACE}(f)$. So you can't hope to prove $L\notin\mathrm{DSPACE}(f)$ as a generic result.

Second, saying "I don't know any languages in $\mathrm{DSPACE}$" is like saying I don't know any people who weigh kilograms (or pounds, if you prefer). It doesn't really mean anything until you specify how many kilograms or, correspondingly, what space bound you're talking about.


"Smallest set" term in the trees set definition I often meet such kind of the definition of the set of trees, as:

The set of unranked $\Sigma$-trees, denoted by $T$, is the smallest set of strings over $\Sigma$ and the parenthesis symbols ‘)’ and ‘(’ such that for each $a\in\Sigma$ and $w\in T^*$, $a(w)$ is in $T$. (http://dl.acm.org/citation.cfm?id=2101368)

One question that I can not generally understand is: how does this definition prevent from the string, say "$a)($", appear in the set $T$?

Would somebody be so kind explain me this point?

And please, if you are going to downvote this question, be so kind explain why are you doing that.

The set of unranked $Σ$-trees, denoted by $T$, is the smallest set of strings over $Σ$ and the parenthesis symbols ‘)’ and ‘(’ such that for each $a∈Σ$ and $w∈T^∗$, $a(w)$ is in $T$.

What we have here is an inductive definition. The base case is implicit because $\epsilon \in T^*$ even if $T = \emptyset$; making is explicit, the definition is (reading $a$ as free variable):

$\qquad\begin{align*}
&\ \phantom{\implies}\ a() \in T \\
 w \in T^+ &\implies a(w) \in T
\end{align*}$

The term "smallest set" is established, but somewhat silly, since all these sets are infinite; we mean the minimal set. Formally speaking, it's the smallest fixed point of this inductive definition; see here and here for some more on that.

As for you question, imagine this definition unfolding in an infinite process:

$a \in T \implies a(a) \in T$.
$a(a) \in T \implies a(a(a)) \in T$.
... and so on...

All you can ever do is wrap things in parentheses; thus you can never creates mismatching pairs like you propose.

A formal proof would be an induction along the inductive definition, of course!

Base case: all alphabet symbols have matching parentheses.
Inductive step: taking elements of $T$ with matching parentheses, those that are "one step larger" have matching parentheses as well.


Constructive Proof on Regular Languages As an assignment, I've to come up with constructive proofs for the following languages to be regular supposing A and B are two distinct regular languages.

$$L_1=\{w│w^R∈A\}$$
$$L_2=\{w│w=a_1 b_1,…,a_k b_k;a_i∈A,b_i∈B\}$$
$$L_3=\{xy│yx∈0A\}$$
$$L_4=\{w│w∈A,∄y∈B:w=xyz for some x,z∈Σ^* \}$$
$$L_5=\{w│∃x∈B:wx∈A\}$$

I've already come up with answers for the first two, but I've no idea about the rest. For L3 no information on what x and y are is provided, so I thought they must be strings concatenated together.

My main question is, is there any generalized algorithm which by using it one can derive an appropriate NFA or RegEx to prove that such languages are regular? Could these things be broken down into primitive structures or operators by some rules or methods so the corresponding NFA or RegEx for the constructive proof be derived from it?

In general, the answer is usually "no". Equality of languages is, most of the time, undecidable; regular languages are a special case here, at least when they are given in certain representations.

What you can do is to break down those languages in terms of closure properties of REG, e.g. reversal, homomorphism, complement, etc.

Since your task here is to prove such closure properties, you'll have to take the long and creative route: come up with a construction and prove it correct. The purpose of the exercise is to train doing exactly that, so taking a shortcut would be unwise.


Calculate Complexity, loop incremented by log(k) I'm preparing for an exam, and I ran across the following algorithm:

for(int j = 1 to n) {
    k=2
    while (k < n) {
        sum+= a[k] * b[k]
        k+= log(k)
    }
}

I'm trying to work on finding the complexity of the algorithm. Here's what I have so far.

The outside loop obviously runs in n steps.
The inside loop gets incremented by log(k), so it should run faster than n as log(n) when n >= 2 is greater than 1. Overall, it looks like the overall complexity is a little faster O(n^2), but by how much? I guess the question boils down to: How do I find the complexity of the inner loop when it is incremented by a function of k? What is the final complexity in this case? I'm assuming O(n^2) is technically correct since it will still be an upper bound, but is there a more accurate answer here?

Let's ignore the outer loop, and concentrate only on the inner one. Since $\log m \approx \log (2m)$ for $m \geq 2$, we see that the number of times it takes $k$ to double is proportional to $k/\log k$. Therefore the number of iteration it takes to get from $2$ to $n$ (assuming for simplicity that $n$ is a power of $2$) is roughly
$$
\frac{2}{\log 2} + \frac{4}{\log 4} + \frac{8}{\log 8} + \cdots + \frac{n}{\log n} \approx \frac{n}{\log n},
$$
since the numbers increase exponentially. Therefore the inner loop runs in time $O(n/\log n)$.

You can make this reasoning rigorous with enough effort.


How exactly does a Max 2 Sat reduce to a 3 Sat? I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after ci is satisfied, 7 out of 10 clauses are satisfied and if it is not satisfied, the 6 out of 10 clauses are satisfied.

Can someone explain to me in simple terms, and demystify what exactly the article wants to convey? Essentially, I have come to know that a max-2-sat problem is the same as a 3 sat problem. The question is I'm not able to understand why.

More formally, I wish to solve this problem:

  Consider the problem MAX2SAT described as follows.
  Given a 2-CNF (Conjunctive Normal Form) Boolean expression  (with m
  clauses, n variables) and an integer k, Decide if there is an
  assignment satisfying at least ‘k’ of the total clauses? Compute the
  complexity class (P or NP or NP Complete) of the MAX2SAT with
  justification.

It seems that the lecture note has abused the symbol $c_i$. You should check the original paper.

Replacing each clause $C_i = (a_i \lor b_i \lor c_i)$ of 3CNF by the collection of 2CNF clauses:

$$(a_i), (b_i), (c_i), (d_i), (\bar{a_i} \lor \bar{b_i}), (\bar{a_i} \lor \bar{c_i}), (\bar{b_i} \lor \bar{c_i}), (a_i \lor \bar{d_i}), (b_i \lor \bar{d_i}), (c_i \lor \bar{d_i})$$

where $d_i$ is a new variable.

  Theorem: If an assignment $\alpha$ satisfies $C_i$, then exactly seven of the ten clauses in the 2-CNF collection can be satisfied.

Proof: $\alpha$ satisfies $C_i$, then either one, two, or three of $a_i, b_i, c_i$ must be true. In all cases, there is a truth setting for $d_i$ causing exactly seven of the clauses to be satisfied. For example, suppose $a_i = \top, b_i = c_i = \bot$, then $d_i = \bot$ causes 7 clauses to be satisfied.

  Theorem: If an assignment $\alpha$ does not satisfy $C_i$, then exactly six of the ten clauses can be satisfied.

Proof: $\alpha$ does not satisfy $C_i$, then $a_i = b_i = c_i = \bot$. In this case, if $d_i = \top$, 4 clauses are satisfied; if $d_i = \bot$, then 6 clauses are satisfied.


Chandy/Misra dining philosophers solution So based on the Chandy/Misra section in this Wikipedia article we've got 5 philosophers numbered P1-P5.
Based on this quote:

For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirty or clean. Initially, all forks are dirty
When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so.

So with the knowledge that all forks are initially dirty, regard the following quote and the image underneath it.

For every pair of Swansons, give the fork to the guy with the smaller id.

My question is if P3 now requests a second fork from his neighbor P4, will P4 give up his single fork beacause it was dirty, even though he just picked it up?

Yes. Whenever a philosopher asks for a fork that is dirty, the philosopher who currently has that fork cleans it and gives it to the person who asked for it.

So, in the initial position, 1 has two dirty forks and can eat, 2, 3 and 4 have one dirty fork each and 5 has no forks at all. If 3 requests a fork from 4, 4 cleans it and gives it to him. This leads to the state where 1 has two dirty forks and can eat, 2 has one dirty fork, 3 has one clean fork and one dirty fork and can eat, and 4 and 5 have no fork.


How a Symbolic Evaluator Generates Test Input for this Example Say we have some complicated function that determines if a string matches an XSS attack string, and throws an error or does something else in that case.

function somethingWithXSSVulnerability(x) {
  var regex = /<script(.*)>(.*)<\/script>/
  if (x.match(regex)) {
    throw new Error('XSS')
  } else {
    return x
  }
}

In trying to understand symbolic evaluation in regards to test generation, I am wondering how it would generate a test for this case. How it would generate an x such that it matched the regex. It could be a lot more complicated than a regex, a grammar for example. The test case generating the error would be something like:

// yes case
somethingWithXSSVulnerability('<script>alert("foo")</script>')
// no case
somethingWithXSSVulnerability('anything else even <script> w/o closing tags')

To really test it, it might need to generate an alert or try setting a cookie or something, so there it is becoming even more complicated.

But I am trying to get a sense of how the symbolic evaluator generates a test for this case. How it determines the value of the input to the function. It seems like it would have to understand the structure of the regex, then reverse-engineer an input to match it. Wondering if that is so.

Tools that solve problems like this often use a SMT (Satisfiability Modulo Theories) solver. This a SAT solver combined with a "theory solver" that can understand operations in some domain.

For example, constraints involving = and != can be decided using union find; constraints involving < on numbers can be decided using the simplex algorithm.

Operations on strings are trickier. Searching "regex string constraint" on Google Scholar finds many papers discussing approaches.

The abstract of this survey papers gives a very brief preview From An Evaluation of Automata Algorithms for String Analysis but notes there is no consensus on a single algorithm (emphasis mine):

https://doi.org/10.1007/978-3-642-18275-4_18

  There has been significant recent interest in automated reasoning techniques, in particular constraint solvers, for string variables. These techniques support a wide variety of clients, ranging from static analysis to automated testing. The majority of string constraint solvers rely on finite automata to support regular expression constraints. For these approaches, performance depends critically on fast automata operations such as intersection, complementation, and determinization. Existing work in this area has not yet provided conclusive results as to which core algorithms and data structures work best in practice.

It seems the best way to algorithmically process regexes is to operate on the NFAs/DFAs that they represent, and, judging by the number of papers on it, there are effective algorithms for making the required decisions.

HAMPI seems to be an important early paper describing how this can be done, which is provided online by one of the authors:
https://homes.cs.washington.edu/~mernst/pubs/string-solver-tr004.pdf


What does it mean to say that there doesn't exist an algorithm from a TM point of view? A TM for a recursive language corresponds to our informal notion of an algorithm.

as per Automata Theory, Languages and Computation by Ullman et al. Then there are languages called RE and $L_d$, where there exist TM that halts for accepting strings in the case of RE languages.

This means that we cannot construct a algorithm for RE languages that are not recursive? Then what is the significance of these RE languages from an algorithm point of view.

What confuses me is that for RE language you can construct a TM. So you can construct an algorithm?

First, note that it is easy to write algorithms that not always halt:

algo(n) {
  while ( n % 2 != 0 ) {
    n += 2
  }
  return n
}

It seems that you are asking for a semi-decidable problem of practical relevance. Consider verification of hard- and software. Many interesting properties require logics of higher order for their formulation, and usually satisfiability and/or validity of such formulae is undecidable.

But these logics have proof system, sets of axioms and rules that make up every proof for valid formulae¹. Along these systems, all proofs can be (recursively) enumerated: thus, we can semi-decide many important properties. Using clever heuristics, lots of computational power and human intervention, e.g. by providing key lemmata, many problems can be solved in practice (i.e. for some useful instances) that are theoretically undecidable.

Beware incomplete proof systems.


Using Myhill-Nerode to prove that language is not regular L = {$xy ∈ \{a, b\}^∗ : |x| = |y|$ and x contains the substring aa}

I am trying to prove that this language is not regular using MyHill-Nerode theorem but I am unable to find equivelance classes of this language.
Thanks.

Consider two words $u_i = b^i aa, u_j = b^j aa \in \{a, b\}^\ast$ with $i < j$. We have that $u_i \not\sim_L u_j$ because if you concatenate the word $v = b^{i+2}$ to both words we obtain
$$u_i \cdot v = b^i aa \cdot b^{i+2} \in L \text{, but } u_j \cdot v = b^j aa \cdot b^{i+2} \notin L.$$
Thus, $v$ separates $u_i$ and $u_j$ for $L$. Since we can find infinitely many $i, j \in \mathbb{N}$ with $i < j$ we have also infinitely many Myhill-Nerode-equivalence classes.


Inequality caused by float inaccuracy At least in Java, if I write this code:

float a = 1000.0F;
float b = 0.00004F;
float c = a + b + b;
float d = b + b + a;
boolean e = c == d;

the value of $e$ would be $false$. I believe this is caused by the fact that floats are very limited in the way of accurately representing numbers. But I don't understand why just changing the position of $a$ could cause this inequality.

I reduced the $b$s to one in both line 3 and 4 as below, the value of $e$ however becomes $true$:

float a = 1000.0F;
float b = 0.00004F;
float c = a + b;
float d = b + a;
boolean e = c == d;

What exactly happened in line 3 and 4? Why addition operations with floats are not associative?

Thanks in advance.

In typical floating point implementations, the result of a single operation is produced as if the operation was performed with infinite precision, and then rounded to the nearest floating-point number.

Compare $a+b$ and $b+a$: The result of each operation performed with infinite precision is the same, therefore these identical infinite precision results are rounded in an identical way. In other words, floating-point addition is commutative.

Take $b + b + a$: $b$ is a floating-point number. With binary floating point numbers, $2b$ is also a floating-point number (the exponent is larger by one), so $b+b$ is added without any rounding error. Then $a$ is added to the exact value $b+b$. The result is the exact value $2b + a$, rounded to the nearest floating-point number.

Take $a + b + b$: $a + b$ is added, and there will be a rounding error $r$, so we get the result $a+b+r$. Add $b$, and the result is the exact value $2b + a + r$, rounded to the nearest floating-point number.

So in one case, $2b + a$, rounded. In the other case, $2b + a + r$, rounded.

PS. Whether for two particular numbers $a$ and $b$ both calculations give the same result or not depends on the numbers, and on the rounding error in the calculation $a + b$, and is usually hard to predict. Using single or double precision makes no difference to the problem in principle, but since the rounding errors are different, there will be values of a and b where in single precision the results are equal and in double precision they are not, or vice versa. The precision will be a lot higher, but the problem that two expressions are mathematically the same but not the same in floating-point arithmetic stays the same.

PPS. In some languages, floating point arithmetic may be performed with higher precision or a higher range of numbers than given by the actual statements. In that case, it would be much much more likely (but still not guaranteed) that both sums give the same result.

PPPS. A comment asked whether we should ask if floating point numbers are equal or not at all. Absolutely if you know what you are doing. For example, if you sort an array, or implement a set, you get yourself into awful trouble if you want to use some notion of "approximately equal". In a graphical user interface, you may need to recalculate object sizes if the size of an object has changed - you compare oldSize == newSize to avoid that recalculation, knowing that in practice you almost never have almost identical sizes, and your program is correct even if there is an unnecesary recalculation.