How to improve my these specific math skills? I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite of the fact that I know how to code I can't solve it. For example, if I don't know the formula for area of circle, I can't find it no matter how good I am at coding.

Have a look at this problem from a programming competition, I did not know how to solve it until Tad posted that it was Assignment Problem and it can be solved with Hungarian Algorithm.After knowing Hungarian Algorithm it was pretty easy to solve. Now you can see problem is with my math skills. I am looking for some resources where I can find such ALL(if not ALL then MOST) algorithms which a programmer/software engineer is supposed to know.

I find it surprising and unfortunate that you didn't get to study algorithms and discrete math more in your university studies. As you seem to have realized, a person can know how to code, but without math, won't be able to solve really interesting problems.

Unfortunately there is no "Learn all algorithms you'll ever need in 21 days for dummies" book. There are hundreds, possibly thousands, of algorithms—even more if you also consider data structures—and it just isn't possible for anyone to know them all. There are no shortcuts to algorithms and math, something which has frustrated me numerous times too. All you can do is throw yourself in and let the knowledge slowly build up.

I would recommend getting yourself a good book on algorithms—my choice would probably be Steve Skiena's The Algorithm Design Manual since it assumes less math background than the more popular Introduction to Algorithms—and a good book on discrete math, of which there are several. I've heard good reviews of Concrete Mathematics but haven't read it as it's a little pricey. Sometimes books use the term "discrete math" in confusing ways; make sure the one you get covers at least graph theory, recurrence relations, Boolean algebra, basic set theory, basic combinatorics, and basic probablity, as those are the most vital topics for a software developer. A book on statistics and probablity, like this one, freely available online and written by a professor from my university, wouldn't go amiss either. And both linear algebra and abstract algebra are useful surprisingly often; I like Gilbert Strang's Linear Algebra and its Applications and Charles Pinter's A Book of Abstract Algebra for these topics.

Of course, just buying these books isn't enough, even if you then proceed to read them. Doing every exercise is a decent start, though probably too dry. I would do exercises until I had drilled down the basics. To really get into these topics, you have to work on problems that use them, which aren't really as hard to find as they might seem. A simple spell checker might calculate Levenshtein distance to suggest corrections for a misspelled word, which allows you to practice dynamic programming. Games and simulations have all sorts of uses for graph algorithms; I implemented the Floyd-Warshall Algorithm in Javascript for a game once, and Dijkstra's Shortest Path algorithm and A* are widely used in games. Project Euler is a great source for number theoretic and combinatorial algorithms. Also make sure not to neglect data structures; try solving some problems that revolve around sets or maps in a lower level language (C, C++, or Java) and implementing your own skip list or red-black tree or hash set. Although these data structures are often available in libraries, the concepts you learn by implementing them are widely applicable (e.g. I never would have understood the Rabin-Karp Algorithm without knowing about hash tables, because it uses hashing, in addition to number theory).

The great thing about this is that not only will you learn algorithms, you'll also get better at coding, and get more familiar with your chosen programming language, by being forced to solve unfamiliar problems. If there's some feature of your language that you've always wanted to use and never been able to, these kinds of exercises are a great way to do that too; I first really dug into Java generics while working on a problem about binary trees.

Finally, just remember that you don't have to know every algorithm off the top of your head. The Hungarian Algorithm in the question you linked is a special purpose algorithm for linear algebra. It's not something most programmers ever have to deal with. Contests do not reflect reality in that way. A contest might expect you to have memorized obscure algorithms and be able to implement them from scratch without any references in a short period of time. When you encounter problems in the wild, it's much more vital that you can clearly state the problem, identify what kind of technique or approach might be helpful, and do research to find something that can solve your problem. In my opinion, it's much more important to look at a problem about matrices, be able to think "This problem is about matrices. I should look at some linear algebra algorithms. Those are probably in a book about numerical algorithms", and then be able to find the Hungarian Algorithm and implement it, than it is to memorize that algorithm and be able to code it off the top of your head.


Speed Up Access to Fractal-Like Array I'm trying to speed up the following function in c++:

void num_to_xy(int num, int *x, int *y):
    *x = (cl & 0x03) | ((cl & 0x10) >> 2) | ((cl & 0x40) >> 3) | ((cl & 0x100) >> 4) | ((cl & 0x400) >> 5) | ((cl & 0x1000) >> 6) | ((cl & 0x4000) >> 7);
    *y = ((cl & 0x0c) >> 2) | ((cl & 0x20) >> 3) | ((cl & 0x80) >> 4) | ((cl & 0x0200) >> 5) | ((cl & 0x0800) >> 6) | ((cl & 0x2000) >> 7) | ((cl & 0x8000) >> 8);

which basically converts num to an x,y coordinate.  This is equivalent to getting the x,y position of num in the following array

$\left| \begin{array}{ccc}
0 &1 &4 &5 &16 &17 &20 &21 &...\\
2 &3 &6 &7 &18 &19 &22 &23 &...\\
8 &9 &12 &13 &24 &25 &28 &29 &...\\
10 &11 &14 &15 &26 &27 &30 &31 &...\\
32 &33 &36 &37 &48 &49 &52 &53 &...\\
34 &35 &38 &39 &50 &51 &54 &55 &...\\
40 &41 &44 &45 &56 &57 &60 &61 &...\\
42 &43 &46 &47 &58 &59 &62 &63 &...\\
\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &
\end{array} \right|$

The array above follows a pattern where for all $k,n$, all numbers between $k4^n$ and $(k+1)4^n-1$ form a perfect square.

Can the code above be sped up without generating a ginormous list and storing all the values?  Or is there a completely different, faster method?

I think that the fastest approach with modern CPUs is

i = num & 255
j = num >> 8
*x = x1[i] + x2[j]
*y = y1[i] + y2[j]

That is 4 arithmetic ops plus 4 loads


Is $L$ always context free? Consider formal language $L$ over finite alphabet $\Sigma$ consisting of all words over $\Sigma$ that have non-trivial period (non empty prefix that is also a suffix). Is $L$ always context free?

Maybe pumping lemma will do? I was advised to try with a word $a^Nb^Na^Nb^N$ but if I pump only second block of $a$ then this word still is in $L$, because it has non empty prefix $a^Nb^N$ that is also a suffix.

Try to use closure properties instead.

Closer hint:

   CFL is closed against (pre)image of language homomorphisms and intersection with regular languages.


3-Coloring Problem Question So I understand that finding a solution to the 3-coloring problem takes exponential time.  However, say you had a friend who you could give a graph G to and he can say in constant time whether it is 3-colorable or not.  Is it possible to find a 3-coloring of G in polynomial time with his help? I think it might be possible but I'm not sure if my approach is correct.

Say the 3 colors are RGB.  You assign some vertex R and give G back to your friend.  If he says Yes, then keep it colored R, if No then leave it be.  Go through every vertex this way assigning R, and then with G and B afterwards.  The graph will be 3-colored at the end, but this would only take O(V*3) time.

First, it is not known that 3-coloring takes exponential time. Even if P is different from NP, it could still be the case that 3-coloring can be solved in subexponential time, though the Exponential Time Hypothesis (ETH) precludes this possibility (if you assume the hypothesis).

Second, regarding your suggested solution. The black box only accepts graphs, it doesn't accept partially colored graphs. You need to give a reduction which only feeds the black box  actual graphs.

Third, if a graph is 3-colorable, then there is always a 3-coloring in which a particular vertex is red. So what you're really trying to do is ask whether there is a 3-coloring in which a given set of vertices has the same color, another set of the vertices has a different color, and yet another one has the remaining color. See if you can somehow encode some of these constraints using graphs rather than partial colorings.


MIPS CPU (Single Cycle MIPS Processor)-R Type instruction ALUOp code confusion I have question about the ALUOp control signal.

When doing R type instructions, 31-26th bits are all 000000.
What decides the instruction is actually the func field of 5-0th bits.

In that case, I wonder why the ALUOp signals for the R type(add,sub,and,or,slt) below the table should all differ. I don't know why ALUcontrol needs to receive data from both instruction and Control when ALUOp for R type looks useless.

Can't ALUcontrol tells ALU what operations to do by just receiving 5-0th bits?
If so, all the ALUOp signal can be all same for the R type.

Thanks in advance!

First, there is a source of confusion between the table you're showing and the diagram.  The table and diagram both use the term "ALUOp" but for the diagram this is the term for the output of the "Control" going into the "ALU control", whereas for the table this is the term for the output of the "ALU control" going into the ALU!

  Can't ALUcontrol tell ALU what operations to do by just receiving 5-0th bits? If so, all the ALUOp signal can be all same for the R type.

Not directly, it doesn't appear so.  I don't see a simple bit pattern in the bit 5-0 that would result in the proper "ALUOp" shown in the table, so a lookup is necessary, which is what "ALU control" is doing when the ALUOp coming from Control is for 000000 (R-type).

  I don't know why ALUcontrol needs to receive data from both instruction and Control when ALUOp for R type looks useless.

This is because "ALU control" is also used by I-type instructions — lw & sw, addi/u, which use the add function of the ALU in computing an effective address, as well as slti, andi, ori, xori, which also require the ALU.  Note that the ALUOp for lw & sw is 010, the same as add (as they use the ALU to compute the effective address).  Further note that the ALUOp for sub and beq are also 110, which makes sense because a beq is comparing the two (albeit for equality, so xor might also have been used).

We don't see the other I-type instructions in the table, but you can imagine the slti/u also use ALUOp 110 for subtraction and addi/u also use 010 for addition, and that, andi, ori, xori, use the same codes as and, or, xor.

The J-type instructions have their own dedicated adders so, no need for ALUOp.


Turn one string into another with single letter substitions I want to turn one string into another with only single letter substitions.  What is a good way to do this, passing through only valid words in between (this website has some examples)?

Valid here means "a word in English" as this is the domain I consider.

My current idea is that I could use a shortest path algorithm with the Hamming distance for edge weights. The problem is that it will take a long time to build the graph, and even then the weight is not so precise in terms of distance (though it will never underestimate it) unless the weight is one, so I would probably have to find a to build a graph that only had weights of one.

What would be the easiest way to build the graph? Am I taking entirely the wrong approach?

The graph I consider has the valid words for vertices and edges correspond to one-letter substitutions. In this graph the Hamming distance never overestimates the distance but can underestimate it (e.g. between $aa$ and $cc$ in the set of valid words ${aa,ab,bb,bc,cc}$)

You don't need an actual graph, you just need a representation of it. The hard part is computing the neighbors : you may want to store the valid words into a prefix tree. But for the search algorithm you already have a non-overestimating distance so you can use that as a admissible heuristic for the $A^*$ algorithm. You can use an hash table to store the marked vertices.

Building the prefix tree

To list all the neighbors of $w$ first use this function that computes all words $v$ such that $w$ and $v$ differs only on the $i$th letter. It runs in $O(|Σ||w|)$ if you implement it correctly : $w$ must be in the form of a list for the tail() dans head() operation to be in constant time. The operation prefix . c . tail(w) just has to be in linear time.

neighbors(i, prefix, w, trie) =
  if(i == 0) :
    for c in 'a' .. 'z' :
      if(tail(w) is a word of trie) :
        add(prefix . c . tail(w))
  else :
    neighbors(i-1, prefix . w[0], tail(w), trie[head(w)])

Then to list all the neighbors, just run:

for i in 0 .. length(w) - 1 :
  neighbors(i, emptyprefix, w, trie_of_valid_words)

Which runs in $O(|Σ||w|^2)$.

Compared to other methods, where $N_V$ the number of valid words.

if you use a hash table and enumerate all the potential neighbors: $O(|Σ||w|^2)$ in the practical case and $O(|Σ||w|^2N_V)$ in the worst case. It might be faster in practice though.
if you use a binary search tree: $O(|Σ||w|\log N_V)$ in the worst and average case.

Precomputation

At first the goal was to get all the neighbors in only one look up in time $O(|w|)$ by previously having computed some kind of prefix tree with wildcards. (I don't really know the name of this data structure) Then I realized that it can simply be done with just a reverse search.

I insist that this is only interesting if you only care about the look up time. I would probably be a good idea if you have to find the shortest path between several pairs of words. If it's only one time the method above will be enough.

This is really very simple : for each word $w$, enumerate all the possible neighbors $v$ of $w$ and check if they are valid. This is in $O(N_V\log N_V |w||Σ|)$ or $O(N_V^2)$ if $N_V$ is small enough for this to be interesting. Add them to your automaton / prefix tree / hash table with the key $v$ and the value $w$.

Then getting all the neighbors of $v$ is looking up in this structure and getting back all the $w$'s. So you can make your search algorithm with this.

Implementation details:

generic binary tree : look up in $O(\log(N_V|Σ||w|))$ which is $O(|w|+\log|Σ|)$ but you don't care about the $\log|Σ|$.
trie : look up in $O(|w|)$
hash : look up in $O(|w|)$ (and worst worst case)

Conclusion

If the set of valid words does not change I would suggest precomputing and storing in a hash table and using the A* with the hamming distance admissible heuristic.


Reducing the infinite language problem to halting problem Let: $INF = \{ w \in \Sigma^* | \quad |L(M_w)| = \infty \} $.

It is easy to show with Rices theorem that $INF$ is not decidable.
($INF$ is non-trivial because of $\emptyset$ and $\Sigma^*$).

How can you show this with a reduction onto the halting problem (for example)?

Here are my thoughts:

I had an idea of running the decider of $INF$ in its own input, but couldnt get very far.

Another idea that I just had was:

Construct a Turing machine TM M' that halts if the language is finite, and loops endlessly if it is infinite:

M'(w):
for i=0,1,...
    simulate M_w on w_i

Knowing the halting problem we cannot know if that turing machine will halt or not. We have supposedly reduced $HALT$ on $INF$. Is this correct ? (Since we take an instance of $HALT$

Can I get some feedback on my solutions ?

Your language is actually $\Pi_2^0$-complete, and in particular even harder than the halting problem.

We can show that $\mathrm{INF}$ is $\Pi_2^0$-hard by reduction from $\mathrm{TOT} = \{ w : L(M_w) = \Sigma^* \}$. Indeed, given a Turing machine $M$, we can construct a Turing machine $M'$ which on input $x$, simulates $M$ sequentially on all inputs $y \leq x$ (using lexicographic order). It is not hard to check that $M'$ halts on infinitely many inputs iff $M$ halts on all inputs.

To show that $\mathrm{INF}$ is in $\Pi_2^0$, notice that a machine $M$ halts on infinitely many inputs if and only if for all inputs $x$ there exists an input $y \geq x$ and a number $n$ such that $M$ halts on $y$ within $n$ steps. Since the last condition is decidable, it follows that $\mathrm{INF}$ is in $\Pi_2^0$.

To answer the question you are interested in, all you need to do is to find a reduction from the halting problem to $\mathrm{TOT}$.


Konig's Theorem for Min Weight Vertex Cover? Koning's theorem states that the cardinality of the maximum matching in a bipartite graph is equal to the size of its minimum vertex cover.

Wikipedia states that there is an equivalent version of the theorem for weighted graphs as well. I tried searching in a lot of places but could not find this theorem.

To be more specific, I want to know what is the equivalent version of Konig's theorem in the case of Minimum Weight Vertex Cover in Bipartite Graphs where each vertex $v \in G$ is assigned a weight $w_v$ and the task is to find a vertex cover of the minimum possible weight.

If the equivalence is just the maximum weighted matching in $G$, what are the weights of the edges in this graph? Because as far as I understand, we have only assigned weights to the vertices of the graph $G$.

Thank you for your time :)

So I found the answer.

The equivalence is that the min weight vertex cover of a bipartite graph can be computed as the maximum flow in a related bipartite graph. In the unweighted case, this maximum flow corresponds to the maximum carnality matching in a bipartite which is exactly the version of Konig's theorem that we all know and love.

For the sake of completeness here is the reduction of bipartite min weight vertex cover to max flow.

Let $G = (A,B)$ be the given bipartite graph. Construct a flow network $N$  by connecting the a source $S$ to all nodes in $A$ and all nodes in $B$ to a sink $T$.

Let the capacity of all original edges in $G$ be $\infty$. The capacity of all edges of the form $(S,a)$ where $a \in A$ will be $w_a$ and the similarly the capacity of all edges $(b, T)$ where $b \in B$ will be $w_b$. Every $S-T$ cut in this network corresponds to exactly one vertex cover and every vertex cover corresponds to an $S-T$ cut. Thus the min-cut a.k.a. the maximum flow will give us the minimum weight vertex cover.

For a more detailed proof refer this.


Parallel programming models: Why do OpenMP and MPI dominate? In a lecture on HPC parallel programming (for CPUs) we discussed various models available from Pthreads to OpenMP to MPI and others like Charm++, X10, UPC, Chapel…. The main focus was clearly on the first three. Intrigued by the topic I did some research on my own but could find sources, examples and discussions mainly for those first three. Later I discovered "AMPI" which can even run legacy MPI application with many of the benefits Charm++ offers but nobody seems to use it.

Why are the other models so neglected? Compared to the rather crude MPI alternatives like Charm++ and UPC appear more convenient as they handle a lot of the "dirty work" neatly in the background.

I will give you two main reasons why MPI and OpenMP dominate.

The first one is that they are standards. There are several available implementations, and you can be sure to find them available on every possible supercomputer machine. This is strictly related to the concept of portability: you write your parallel code and, if you do not use anything else related to a particular machine, you can run the same code on all of the parallel machines you have available.

The second reason is the programmer's resistance. With MPI and OpenMP covering both message-passing and shared-memory parallel programming (and you can even use them simultaneously if useful and/or required) why a programmer, especially a beginner in the field, should spend his/her time learning new parallel programming languages that are not granted to become standards? Sure, as you pointed out, other languages provide some benefits but the question is, would you invest your time betting on something that may even totally disappear in the future ? Standards are here to stay. Anyway, regarding this specific point, my humble opinion is that, if possible, one should instead spend some time on different languages (not just those one for parallel programming) because this is a useful discipline and learning different paradigms is always beneficial. However, when reading your curriculum vitae for possible hiring, the people that can hire you for a position will be in general mostly interested to your knowledge of the standards, not to your knowledge of niche languages (in general, even though there could be exceptions of course).


Shift-and-or multiplication operation Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold):

Let $r = p \oplus q$ be an operation similar to multiplication, but slightly simpler: when expressed via long-multiplication the columns aren't summed up, but rather or'd (not xor) together. Nothing is carried.

$$
  \left[\begin{matrix}
    &&p_n & ... & p_i & ... & p_2 & p_1 \\
    &&q_n & ... & q_i & ... & q_2 & q_1 & \otimes\\
    \hline\\
    &&q_1 \cdot p_n & ... & q_1 \cdot p_i
      & ... & q_1 \cdot p_2 & q_1 \cdot p_1\\
    &q_2 \cdot p_n & ... & q_2 \cdot p_i
      & ... & q_2 \cdot p_2 & q_2 \cdot p_1\\
    &&&&&&&...\\
    q_i \cdot p_n & ... & q_i \cdot p_i
      & ... & q_i \cdot p_2 & q_i \cdot p_1 & \stackrel{i}{\leftarrow}
      &&{\bigvee} \\
    \hline \\
    \\r_{2n}& ... & r_i
      & ... &r_4& r_3 & r_2 &r_1 & =
  \end{matrix}
  \right]
$$

Using the long-multiplication-style formulation, this takes $\mathcal O\left(\max\left(\left|p\right|,\left|q\right|\right)^2\right)=\mathcal O\left(\left|r\right|^2\right)$ time. Can we do better? Perhaps we can reuse some existing multiplication algorithms, or even better.

This is equivalent to an operation known as boolean convolution. See Models of Computation page 419 defn 9.6.3.

Dunne states (p5):

  Weiss 1984 and Blum 1984b obtained lower bounds for the n-point boolean convolution function which is closely related to integer multiplication.

Models of computation
Relationships between monotone and non-monotone network complexity, Dunne
Blum, N. (1984b) An $\Omega(n^{4/3})$ lower bound on the monotone network complexity of n-th degree convolution; Theoretical Computer Science, 36, 59-70


Why are comparisons so expensive on a GPU? While trying to improve the performance of my collision detection class, I found that ~80% of the time spent at the gpu, it spent on if/else conditions just trying to figure out the bounds for the buckets it should loop through.

More precisely:

each thread gets an ID, by that ID it fetches its triangle from the memory (3 integers each) and by those 3 it fetches its vertices(3 floats each).
Then it transforms the vertices into integer grid points (currently 8x8x8) and transforms them into the triangle bounds on that grid
To transform the 3 points into bounds, it finds the min/max of each dimension among each of the points

Since the programming language I am using is missing a minmax intrinsic, I made one myself, looks like this:

procedure MinMax(a, b, c):
   local min, max

   if a > b:
      max = a
      min = b
   else:
      max = b
      min = a
   if c > max:
      max = c
   else:
      if c < min:
         min = c

   return (min, max)

So on the average it should be 2.5 * 3 *3 = 22.5 comparisons which ends up eating up way more time than the actual triangle - edge intersection tests (around 100 * 11-50 instructions).

In fact, I found that pre-calculating the required buckets on the cpu (single threaded, no vectorization), stacking them in a gpu view along with bucket definition and making the gpu do ~4 extra reads per thread was 6 times faster than trying to figure out the bounds on the spot. (note that they get recalculated before every execution since I'm dealing with dynamic meshes)

So why is the comparison so horrendously slow on a gpu?

GPUs are SIMD architectures.  In SIMD architectures every instruction needs to be executed for every element that you process.  (There's an exception to this rule, but it rarely helps).

So in your MinMax routine not only does every call need to fetch all three branch instructions, (even if on average only 2.5 are evaluated), but every assignment statement takes up a cycle as well (even if it doesn't actually get "executed").

This problem is sometimes called thread divergence.  If your machine has something like 32 SIMD execution lanes, it will still have only a single fetch unit.  (Here the term "thread" basically means "SIMD execution lane".)  So internally each SIMD execution lane has a "I'm enabled/disabled" bit, and the branches actually just manipulate that bit.  (The exception is that at the point where every SIMD lane becomes disabled, the fetch unit will generally jump directly to the "else" clause.)

So in your code, every SIMD execution lane is doing:

compare (a > b)
assign (max = a if a>b)
assign (min = b if a>b)
assign (max = b if not(a>b))
assign (min = a if not(a>b))
compare (c > max)
assign (max = c if c>max)
compare (c < min if not(c>max))
assign (min = c if not(c>max) and c<min)

It may be the case that on some GPUs this conversion of conditionals to predication is slower if the GPU is doing it itself.  As pointed out by @PaulA.Clayton, if your programming language and architecture has a predicated conditional move operation (especially one of the form if (c) x = y else x = z) you might be able to do better.  (But probably not much better).

Also, placing the c < min conditional inside the else of c > max is unnecessary.  It certainly isn't saving you anything, and (given that the GPU has to automatically convert it to predication) may actually be hurting to have it nested in two different conditionals.


Halting Problem and Turing Degree and Reduction? This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question.

  for $ A \subseteq \mathbb{N}$ we have $a=deg_T(A)=\{B | B \equiv_T A \} $ and $D=\{deg_T(A)|  A \subseteq \mathbb{N} \}$. For $(D, \leq)$
  that has $A \leq_T B$ iff $ a \leq b$. which of the following is
  false:

  1) $(D, \leq)$ is a distributive lattice

  2) $(D, \leq)$  is bounded (has minimum and maximum)

  3) $(D, \leq)$ is a half disjunctive lattice. (may be I worded this
  statement poorly, sorry)

  4) he maximum elements of $(D, \leq)$ is a degree of Halting Problem .

I think $deg_T$ means Turing Degree and $\leq_T$ means Turing Reduciblity.

Edit 1:

To complete LogicLove's answer, the solution for (1) can be found in a math.se question.

As there are pairs of degrees which have no greatest lower bound, the conditions for a distributive lattice can't be met.


Pre-requisite knowledge before diving into algorithms I'm having some difficulty trying to follow what the authors of some of the more highly recommended books on algorithms. I ran into the same problem when trying out some online courses. My goal is to prepare myself to start learning fundamental algorithms for use in low-level languages by means of understanding them mathematically. So far, a guide on wiki is a good resource to decipher the symbols, but I'm not sure that will suffice.

Is there anything besides this page that a person would need before learning algorithms besides basic algebra concepts?

To learn algorithms mathematically you will need to have a basic understanding of

Proofs(basically using induction)
summations and
asymptotic notations(like Big-O , Big-Omega)

To learn the above subjects I recommend this course from  https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/


Decidable product with an undecidable projection I got some problems with building a set, which should looks like this: $S = A\times B \subset N \times N $, where $S$ is decidable but $A$ is undecidable.

Could somebody give me a clue how to actually do this?

Let $A$ be set of Turing machines that halt, which is clearly undecidable. Now $B$ needs to be something that helps you decide $A$ (a certificate if you will, in the sense of a certificate for a $NP$ problem). Hint: if a TM halts, it halts in a finite number of steps.


Efficiently selecting the median and elements to its left and right Suppose we have a set $S = \{ a_1,a_2,a_3,\ldots , a_N \}$ of $N$ coders.

Each Coders has rating $R_i$ and the number of gold medals $E_i$, they had won so far.

A Software Company wants to hire exactly three  coders to develop an application.

For hiring three coders, they developed the following strategy:

They first arrange the coders in ascending order of ratings and descending order of gold medals.
From this arranged list, they select the three of the middle coders.
E.g., if the arranged list is $(a_5,a_2,a_3,a_1,a_4)$ they select $(a_2,a_3,a_1)$ coders.

Now we have to help company by writing a program  for this task.

Input:

The first line contains $N$, i.e. the number of coders.

Then the second line contains the ratings $R_i$ of $i$th coder.

The third line contains the number of gold medals bagged by the $i$th coder.

Output:

Display only one line that contains the sum of gold medals earned by the three coders the company will select.

This is a problem of selecting the $k$th smallest element from the list solved by a class of algorithms called the Selection Algorithms. There exist deterministic linear time selection algorithms so your problem can be solved in linear time by selecting the $n/2,n/2-1,n/2+1$th smallest elements from the original unsorted list.


Why does an admissible heuristic mean A* is optimal? An admissible heuristic never overestimates the cost to reach the goal. However, isn't that only the relative difference between heuristics for two different paths matter?

Say we have optimal path A (cost 100 to reach goal) and sub-optimal path Z (cost 120 to reach goal). Even if the heuristic is admissible, say it gives A a heuristic of cost 99 while it gives Z a heuristic of cost 10.

In both cases, the heuristic is admissible since it's lower than the actual cost it'll take to reach the goal, but still under this, Z is optimal since the heuristic gives a cost of 10 to Z and a cost of 99 to A.

It seems to me then it doesn't even matter that the heuristic is admissible. You still get the suboptimal solution.

What am I missing?

With an admissible heuristic

The heuristic defines which nodes will be explored first, but does not change the final path found.

In your example, the heuristic will cause the path to Z to be explored first.  The algorithm will discover the true (expensive) cost of 120.  Then it will decide to explore the A path and discover the optimal route.

A better heuristic would guess A was the way to go immediately, find the cost of 100, and never bother exploring Z at all (e.g. if the heuristic said the cost was greater than 100).

So the heuristic changes the execution time, but not the final answer.

With an unadmissable heuristic

If the heuristic marked A as costing 130 (when the true cost is 100), it may find the route to Z (true cost 120), and instantly stop (because it "knows" the cost to A is at least 130), so return the wrong answer.


Is language $\{a,b\}^*$ same as language $\{xy \in \{a,b\}^* \mid |x|_a = |y|_b \}$? I need to prove or disprove if these two languages are same.
So I assume that these lanaguages are same because I think that every word from $\{a,b\}^*$ could be concatenated from two words $x$ and $y$ where $|x|_a = |y|_b$. So $x$ and $y$ must belong to $\{a,b\}^*$, too. Then I can write and prove this:

$\{a,b\}^* \subseteq \{xy \in \{a,b\}^* \mid |x|_a = |y|_b \} \wedge \{xy \in \{a,b\}^* \mid |x|_a = |y|_b \} \subseteq \{a,b\}^*$

So I assume that $z \in \{a,b\}^*$. Then $z = z_1z_2...z_i$ where $z_1,z_2,...,z_i \in \{a,b\}$

Here I stucked and I don't know (1) how to continue, (2) if the way of proving i choose is correct or not.

You can prove this by induction on the length of the string.

The base case of $|z| = 0$ is obvious, we have to take $x=y=\varepsilon$.

The inductive assumption then is that $L =\{xy \in \{a,b\}^{\ast}\mid |x|_{a} = |y|_{b}\}$ contains all strings1 of length at most $n$.

Now we want to show that it contains all strings of length $n+1$.

Let $z \in  \{a,b\}^{n+1}$ and let $z^{-1}$ be $z$ with the final symbol removed. By the inductive assumption $z^{-1} \in L$. The final symbol $z_{n+1}$ in $z$ must be either an $a$ or a $b$.

If $z_{n+1}$ is an $a$, then we can construct an appropriate $x_{z}$ and $y_{z}$ by taking $x_{z} = x_{z^{-1}}$ and $y_{z} = y_{z^{-1}}a$. Then $|x_{z}|_{a} = |x_{z^{-1}}|_{a} = |y_{z^{-1}}|_{b} = |y_{z}|_{b}$, and therefore $z\in L$.
If $z_{n+1}$ is a $b$ we have a slightly more complicated situation, but it's not too difficult. The first symbol of $y_{z^{-1}}$ must also be either an $a$ or a $b$, or $y = \varepsilon$.

If the first symbol is an $a$, then we use the same $x$-$y$ partition as for $z^{-1}$, but we move the first symbol of $y$ to the end of $x$, and add the new $b$ to the end of $y$, then $|x_{z}|_{a} = |x_{z^{-1}}|_{a} + 1$ and $|y_{z}|_{b} = |y_{z^{-1}}|_{b} + 1$.
If the first symbol is a $b$, we do the same as in the $a$ case, but as we're adding a $b$ to $x$ and taking one $b$ away from $y$ but adding another at the end, the number of $a$s and $b$s in $x$ and $y$ don't change.
If $y_{z^{-1}} = \varepsilon$, then we simply choose $x = z$ and $y = \varepsilon$ and again $|x_{z}|_{a} = |x_{z^{-1}}|_{a} = |y_{z^{-1}}|_{b} = |y_{z}|_{b}$ (in fact, they all equal $0$, so $z = b^{n+1}$).

Therefore in all cases $z \in L$, and we are done.

Footnotes

...over alphabet $\Sigma = \{a,b\}$.


How to formally prove that if triangle inequality is satisfied in a bunch of edges, then each edge has a positive value? The exact questions states the following:

  Suppose that a complete undirected graph $G = (V,E)$ with at least 3 vertices has cost function $c$ that satisfies the triangle inequality. Prove that $c(u,v) \geq 0$ for all $u,v \in V$.

I can intuitively see that $c(u,v)$ is always positive but I don't understand how to present it in a formal proof. From how I see this, for triangle inequality to hold true, $a+b\geq c$, $b+c\geq a$ and $a+c\geq b$.
From the above, we can obtain that $a+b\geq a-b$, $b+c\geq b-c$, etc. Since, sum is larger than the difference, it seems to be intuitive that all numbers positive.

I found out how to prove that each edge has positive weight. Now the issue is that there could be an edge that is not part of a triangle. Then how to prove that it is also positive? I guess we have to assume the graph to be complete. Otherwise I don't have any idea on how to solve it.

Let us first go into the proof. Let us then review any further considerations as you do (ie., whether the graph should be complete or not).

Lemma Given an undirected graph $G=(V,E), |V|\geq 3$, and a cost function $c$ defined over $E$, if the triangle inequality is satisfied, then $c(u,v)\geq 0, \forall \langle u,v\rangle \in E$.

Note that the lemma does not require the graph to be complete ---a graph is complete if there is an edge for every pair of vertices, i.e., $\langle u, v\rangle\in E, \forall u, v\in V$.

To prove the statement above take any three vertices $u, v, w\in V$ which are related to each other, i.e., that form a triangle. Let $\alpha=c(u,v), \beta=c(v,w), \gamma=c(u,w)$. Let us assume further without loss of generality that these edge costs are sorted in increasing order of cost: $\alpha\leq\beta\leq\gamma$ ---and this order necessarily exists as discrete optimization problems are usually defined over total orders.

Now, let us proof by contradiction the lemma. There are three different cases (all somehow related to each other, if you manage to understand the first, the others are rather equivalent but I wrote them down here for your convenience).

Case 1 (only one negative edge cost)

Assume that $\alpha<0$. Because triangle inequality is assumed by hypothesis then: $\alpha+\beta\geq\gamma$. To make signs apparent, take absolute values: $|\beta|-|\alpha|\geq |\gamma|$, where I considered $\beta, \gamma\geq 0$. Obviously, $|\gamma|\geq |\gamma| - |\alpha|$ and this is true for all plausible values of $\gamma$ (also negative ones). Thus:

$
|\beta|-|\alpha|\geq |\gamma|\geq |\gamma| - |\alpha|
$

leading to $\beta\geq\gamma$ which contradicts our first assumption ($\beta\leq\gamma$).

However, devil's in the details so let us consider the frontier case where $\beta=\gamma$. In this case, take now the other relationship that results from triangle inequality: $\alpha+\gamma\geq\beta$. Since $\beta=\gamma$, the preceding relationship simplifies to $\alpha\geq 0$ which, again, contradicts our second assumption, $\alpha<0$. Hence, $\alpha\geq 0$.

It is straightforward to prove that the same reasoning applies in case $\beta<0$ or, equivalently, that $\gamma<0$. Note, however, that from the order we assumed over these costs, $\beta<0$ implies that there are two edge costs which are negative, and that $\gamma<0$ implies that all of them are negative. These cases are examined next.

Case 2 (two negative edge costs)

Still, there is a caveat in the preceding reasoning. When taking absolute values to make the signs apparent, I considered $\beta, \gamma\geq 0$. You might think that the lemma might not hold in case that two edge costs are negative. Let us assume that both $\alpha, \beta<0$, then as triangle inequality is assumed $\alpha+\beta\geq\gamma$ and again, after taking absolute values the following results: $-|\alpha|-|\beta|\geq|\gamma|$, which is clearly impossible, as the left hand is a negative number and the right hand is a positive number.

And this completes the proof for the second case. If you are thinking of trying the same proof for $\beta, \gamma<0$ or $\alpha,\gamma<0$, note that all edge costs would be necessarily negative as they are sorted in increasing order of cost. This observation leads us to the third case.

Case 3 (all edge costs are negative)

To conclude, what if all edge costs are negative, $\alpha, \beta, \gamma<0$? Oh, well, then it just suffices to combine two expressions resulting from triangle inequality: $\alpha+\beta\geq\gamma$ and, since all of these are negative numbers, then $-|\alpha|-|\beta|\geq -|\gamma|$, but also $\alpha+\gamma\geq\beta$ and, again, because these are all negative numbers then $-|\alpha|-|\gamma|\geq-|\beta|$. Now, the observation is that the first inequality shall hold for values larger or equal than $-|\beta|$ and hence: $-|\alpha|-(-|\alpha|-|\gamma|)\geq -|\gamma|$ which leads to $|\gamma|\geq -|\gamma|$, which is only possible if $\gamma=0$ but this contradicts our assumption that $\gamma<0$ and hence the third case is proven as well by contradiction.

Note to the third case - in case you have difficulty to follow how the last inequality is hold, transform all $\geq$ to $\leq$ by multiplying all inequalities by $-1$. Now, only with positive numbers it might be easier to follow the reasoning.

Observations

Nowhere in the preceding proof I assumed the graph to be complete and, indeed, there might well be a pair of vertices $u,v\in V$ which are not directly related to each other through an edge. What we actually did is to prove that every three vertices connected to each other shall be non-negative given that triangle inequality is verified. This does not prevent some edge costs to be negative. It just suffices that the vertex connected to an edge with a negative cost is not connected to any other vertex. This is true because if the degree of a vertex equals 1 then triangle inequality can not be verified.

Equivalently, if the degree of each vertex is larger or equal than two, triangle inequality can be always verified and, in case it holds, then all edge costs are necessarily non-negative.

Hope this helps,


Example of Soundness & Completeness of Inference Is the following example correct about whether an inference algorithm is sound and complete?

Suppose we have needles a, b, c in a haystack, and have also an inference algorithm that is designed to find needles.

sound - Only needles a, b and c are obtained.
complete - Needles a, b and c are obtained. Other hay may also be obtained.

You have almost got it right, but your definition of soundness is not quite right, or perhaps too subtle.

I would say that the inference algorithm is sound if everything returned is a needle (hence some needles may be missed) and complete if all needles are returned (hence some hay may be returned too).


Dynamic length of union of segments (1d Klee's measure problem) Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of their union. There is a simple $O(n \log n)$ solution involving sorting endpoints of all intervals and then iterating over them while keeping track of some counters.

Now let's look at a dynamic variant of this problem: we are receiving $n$ segments one after another and the task is to find the length of the current union of segments after each new segment arrives. It seems like a natural generalization, however, I cannot find much information about this version of the problem. I wonder if it is still possible to solve this problem in $O(n \log n)$ time in an offline setting, i.e. when we are given all segments beforehand and can preprocess them in some way before giving an answer for each segment.

I feel like a modification of a segment tree might be useful here. In every node we need to keep track of both the total sum of lengths of segments (or their parts) corresponding to this node and the length of their union. However, I cannot figure out how to implement this modification without performance of one update degrading to linear time in some cases. Maybe using a segment tree is not the right approach and a better way exists.

Update:

What if we make the problem even more difficult by also allowing to delete previously added segments? Can it still be solved offline in $O(n \log n)$ time where $n$ is the total number of add/delete segment queries?

The online version can be solved in $O(n\log n)$ amortised time, possibly using the technique you already came up with. The key is to maintain just the nonoverlapping intervals that result from merging intervals wherever necessary.

Maintain an ordered list of the endpoints of segments in a binary search tree, with each endpoint represented by a pair $(x, type)$, where $type$ is either $start$ or $stop$. New intervals will be merged with these so that the segments in the tree are nonoverlapping at all times. When a new segment $[a, b]$ arrives, add $b-a$ to the total length, and search the tree to find all contained endpoints. For each such endpoint:

If it is $(x, start)$, add $x$ to the total length.
If it is $(x, stop)$, subtract $x$ from the total length.
Delete it.

If the leftmost such endpoint is a $start$, or if there are no endpoints, then insert $a$ as a $start$ endpoint; otherwise, if there was at least one endpoint (the leftmost of which must be a $stop$), add $a$ to the total length. If the rightmost such endpoint is a $stop$, or if there are no endpoints, then add $b$ as a $stop$ endpoint; otherwise, if there was at least one endpoint (the rightmost of which must be a $start$), subtract $b$ from the total length.

To understand why the time complexity is not quadratic even though an individual operation can take $O(n)$ time, notice that a preexisting interval never needs to be merged with other intervals more than twice (once to its left, once to its right), so we can conservatively pay the cost of these potential merges at the time we create the interval; since merging amounts to removing an endpoint, the cost of performing a merge is constant, so the overall time complexity doesn't change. Basically, any time we have to merge a bunch of intervals, we remove the possibility of having to merge them in the future.


How do I interpret this divide and conquer algorithm for removing duplicates in a list? Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French.

What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ compared?

As wvxvw suggested, the dot notation is a shorthand way of separating the head and the tail of a list, as in LISP or ML. For example, if we have a list $L=\langle\,4,7,8\,\rangle$ then we can write $L$ as $c_1.c_2$ where $c_1=4$ and $c_2=\langle\,7,8\,\rangle$.

The function $\Delta$ takes two sorted lists, $c_1.c_2$ and $d_1.d_2$ and recursively produces a list without duplicates. For instance, we might have
$$\begin{align}
\Delta(\langle\,6\,\rangle,\langle\,3,5,6\,\rangle) &=\langle\,3,\Delta(\langle\,6\,\rangle,\langle\,5,6\,\rangle)\,\rangle&\text{by rule 3}\\
&=\langle\,3,5,\Delta(\langle\,6\,\rangle,\langle\,6\,\rangle)\,\rangle&\text{by rule 3}\\
&=\langle\,3,5,6,\Delta(\varnothing,\varnothing)\,\rangle&\text{by rule 2}\\
&=\langle\,3,5,6\,\rangle
\end{align}$$
This is where the real work is done. The function $SD$ uses $\Delta$ by splitting the original sorted list $\langle\,s_1,s_2,\dotsc,s_n\,\rangle$ into two: the odd-indexed part, $\langle\,s_1,s_3,s_5,\dotsc\,\rangle$ and the even-indexed part, $\langle\,s_2,s_4,s_6,\dotsc\,\rangle$ and applies $\Delta$ to them, to remove duplicates. For instance,
$$\begin{align}
SD(\langle\,3,3,3,5,6,6\,\rangle&=\Delta(SD(\langle\,3,3,6\,\rangle),SD(\langle\,3,5,6\,\rangle))\\
&=\Delta(\langle\,3,6\,\rangle,\langle\,3,5,6\,\rangle)&\text{since $SD$ removes dups}\\
&=\langle\,3,5,6\,\rangle
\end{align}$$
as we saw above. It's worth noting that the arguments to both functions must be in sorted order. To see why, trace the action on, say, $\langle\,3,4,2,3\,\rangle$.


Divide grid so that each box has only one object Is there an efficient algorithm to divide a 2D space, which contains several different sized rectangles, such that each partition has only a single object. Please see the attached image.

I have come up with a recursive algorithm that cycles through the 2 axis and divide the boxes until there is only one object in a box/partition. The only problem is that the arrangement that I have in mind is actually inefficient and it seems very hard to handle cases in which the rectangles are overlapping. In the case where the rectangles are overlapping, we want all the overlapping rectangles to be inside the same partition.

Another detail, the boxes will always be axis aligned and the partitions also have to be axis aligned.

Any help will be greatly appreciated. Thank you!

I initially missed your remark about overlapping rectangles -- as orlp said in a comment, there's obviously no solution in those cases.  But I had already typed the rest of this answer out, assuming the input has no overlapping rectangles, so I'll leave it here in case it's helpful.

It sounds like your current method repeatedly looks for a guillotine cut: That is, a cut that goes all the way from top to bottom, or all the way from left to right.

Unfortunately, even if you split subproblems at as many places as possible within a single $O(n \log n)$-time scan along one dimension, this can result in $O(n^2 \log n)$ time overall, like for instances such as the following where each scan only succeeds in peeling off a single rectangle:

XXXXX

X   X
X X X
X
X XXX

But the real problem is that some instances can't be solved this way at all, even when no overlapping rectangles are involved.  For example:

XXX X
    X
X   X
X
X XXX


Simulating multi-tape turing machines by single-tape TM In "Computational Complexity: A modern approach", Arora and Barak proof the following Claim:

  Define a single-tape Turing machine to be a TM that has only one read-write tape, that is used a input, work, and output tape. For every $f: \{0,1\}^* \rightarrow \{0,1\}$ and time-constructible $T: \mathbb{N} \rightarrow \mathbb{N}$, if $f$ is computable in time $T(n)$ by a TM $M$ using $k$ tapes, then it is computable in time $5kT(n)^2$ by a single-tape TM $\hat{M}$.

The proof roughly goes like this, from my understanding:

-> We encode the $k$ tapes of $M$ on a single tape, using locations $i,k+i,2k+i$ for the $k$-th tape.

-> For each character $a$ in M's alphabet, we define another character $\hat{a}$ in $\hat{M}$'s alphabet. For each of M's tapes, the $\hat{a}$ character indicates the current position of that respective tape (for $M$) in $M's$ encoding.

-> For each state transition of $M$, $\hat{M}$  then perform two sweeps: One left-to-right, where $\hat{M}$ finds the positions of $M$ at the respective working tapes and one right-to-left where $\hat{M}$ updates its tape encoding according to state transition function of $M$.

Its not clear to me how the first step exactly works. Arora and Barak write:
"First it sweeps the tape in the left-to-right direction and records to its register the $k$ symbols that are marked by $\hat{a}$". As far as I understand, registers correspond to states in the TM $M'$. What is exactly is meant by recording the symbols to its register?

You can simulate a state machine with set of states $S$ and registers $R_1,\ldots,R_m$ varying over a finite alphabet $\Sigma$ using a vanilla state machine whose set of states is $S \times \Sigma^m$. You "store" a value $x$ in register $R_i$ by transitioning to a state whose $(i+1)$'th element is $x$. You "read" a value from $R_i$ by taking into account in your transition table the $(i+1)$'th element of the current state.

This is the sense in which $\hat{M}$ has registers – their contents are stored in the state of the machine. Here it is crucial that both $k$ and the tape alphabet are fixed and finite.


Is it possible to implement a WeakMap with primitive keys and weak values? Theory

Basically, I have a use-case where I would like to use primitives to store weak references to non-primitive values. If the value is no longer referenced anywhere else, then the entry should be GC'd from the WeakMap and checking the primitive key for an existing value would return false.

Is this possible to implement, and how so in a theoretical sense? If not, why isn't it possible to?

Use-case

Since people seem to be confused about the use-case, it's pretty straight-forward. Essentially, consider a function, when given a primitive, generates a non-primitive deterministically using an expensive operation. I expect a fair amount of these generated non-primitives to be used at run-time, and a large percent of them to be re-used.

For the non-primitives that have a reference held onto them, they are used as keys in an operation that coerces them back into the primitive that was used to generate them (this step cannot be avoided, unfortunately), that then must be used to re-generate the non-primitive again.

It would be convenient to have a WeakMap to access the original non-primitive, if it has already been made, instead of using the expensive operation to generate a copy of it, but currently I don't see a way to achieve this.

Okay. My confusion with this question is that I assumed that what you wanted is a weak value map, which it appears is what you want, and this can be implemented in a straightforward manner (at least as straightforward as a weak key map). I'm using (slightly modified) terminology from Designing Efficient and Safe Weak References in Eiffel with Parametric Types.  The JavaScript WeakMap is indeed a weak key map, and, as you seem to understand and D.W. states, it makes no sense to have weak references to primitive values, and thus primitive values as keys in a weak key map.

As far as a weak value map, it's implemented basically the same as a weak key map. For example, for a mark-sweep GC, during the sweeping phase if the GC notices that a value in a weak value map is dead it removes all entries in the map referencing it.  A weak key map is basically the same only it considers the keys.  The Eiffel paper also talks about weak vectors and doubly weak maps where either the key or the value dying results in the entry being removed.

A weak reference primitive as described in the paper or as in e.g. Java's WeakReference would make this a straightforward exercise. You'd just wrap a Dictionary<Key, WeakReference<Value>> to clean out entries on access, say.


Understanding of hash tables I am currently studying hash tables in an introductory course to computer science. I was taught that  hash table is a data structure that associates a key to an index (a hash table) and then to the value associated to the key.

I don't understand why the hash function doesn't directly associate the key to the value

You cannot associate the key to a value directly, since you don't know in advance the set of keys. Hash tables implement an associative array, which is indexed by arbitrary objects. A naive implementation would have a huge array, indexed by all possible values of all possible types of objects. But this is clearly not realistic. Hash tables instead use a hash function to map a key to a numeric index, which is then used to address a conventional array.

If you knew the set of keys in advance, you could implement associative arrays as arrays indexed by the keys (like your suggestion). But it is not clear how to implement this. Suppose, for example, that the keys are all 3-regular graphs on 10 vertices. Given a 3-regular graph on 10 vertices, how do you associate it to a position in your array? It's not clear how to do this efficiently. Using a hash function, however, this becomes very easy.


Which cellular automata rules are suitable for randomizing an input sequence? S. Wolfram has in has book "A New Kind of Science" listed 256 simple rules of cellular automata. Which of these rules could via iteration essentially contribute to render an input sequence more random in a certain sense?

Rule 170, for examples, simply produces a left
shift and evidently is not of use in this, if I don't err. My limited computations with inputs
that are more or less random seem to indicate that the majority of the 256 rules are even contraproductive in this context. How could one best proceed to clarify this issue or are there already relevant published results available?

Rule 30 is probably the "most random" of all 256 rules. It has been used as random number generator, but there are some issues:

Some initial states will result in repetitive output, which is not what we want from a random number generator. However, given that the automaton is large enough, and that the initial state is itself somewhat random, this shouldn't a problem.
There are better ways to generate random numbers.


calculting distance between a person and the object in the image Let's say a person took an image like this

I have access to all image attributes (like for example image format, resolution and so on), and I know the location of the person - basically the place where he made the photo. Also I know all the data about the camera - model, resolution and others.

Is there an algorithm that allows to calculate the real distance between a person and the object on the image?

No, it's not possible without extra information.  Just think: if the house was 20 feet tall and 100 feet away, you couldn't distinguish that from the case where the house was 30 feet tall and 150 feet away.  Those two would lead to exactly the same image.
Here are some possible options you could consider:

If you have two pictures of the same house taken from two different positions, and you know the relative positions (e.g., one was 10 feet to the right of the other), then you may be able to infer the distance to the house, using parallax.

If you know the height of some feature in the image -- say, the door -- and you know all of the camera parameters (in particular, the angular resolution of a single pixel or of the field of view), then you can work out the distance to the house.  So if you could calibrate the camera in advance, and make a guess/assumption about the height of the door, you could draw an inference about the distance to the house.
However this does require knowing all the camera parameters, which will probably require some calibration; I just knowing the image format, resolution, etc. and the camera resolution etc. will not be enough, and even knowing the model of the camera will probably not be enough. (Possibly if you knew the exact model of the camera and could go buy another camera of the same model, you might be able to calibrate the second one and assume both cameras have the same calibration.  I don't know if that would work.)

See also Using Headpose Vector and 2D Points to Compute Distances.  You might also look into camera intrinsics, camera extrinsics, the pinhole camera, and similar topics from computer graphics / computer vision.


Algorithm to sort n numbers from 0 to $n^m$ in $\mathcal{O}(n)$? where m is a constant So i came upon this question where:

we have to sort $n$ numbers between $0$ and $n^3$ and the answer of time complexity is $\mathcal{O}(n)$ and the author solved it this way:

first we convert the base of these numbers to $n$ in $\mathcal{O}(n)$, therefore now we have numbers with maximum 3 digits.

now we use radix sort and therefore the time is $\mathcal{O}(n)$

so i have three questions :

is this correct? and the best time possible?
how is it possible to convert the base of n numbers in $\mathcal{O}(n)$? like $\mathcal{O}(1)$ for each number? because some previous topics in this website said its $\mathcal{O}(M(n) \log(n))$?
and if this is true, then it means we can sort any $n$ numbers from $0$ to $n^m$ in $\mathcal{O}(n)$?

The reason of your confusion is that the computational model under which the algorithm is run is not specified.

Assuming you are allowed to perform arithmetic in $\mathcal{O}(1)$ time$^*$, then the $\mathcal{O}(mn)$ bound is correct. The reason is that you don't need to explicitly make base conversions. Since radix sort only ever compares digits of numbers, it is sufficient to provide a way to compare arbitrary digits in $\mathcal{O}(1)$ time$^{**}$; it is not hard to convince yourself that given an integer $x$, the $i$-th digit from the right in the base $b$ representation of $x$ is exactly:

$\qquad x/b^{i-1} \ \% \ b$

where $\%$ is the modulo operator.

Under more stringent conditions on arithmetic (such as classical random access machines or constantly-bounded Word-RAMs), both taking the modulo and division by a constant are operations that take logarithmic time, changing the running time of radix sort accordingly.

$^*$ For example, with a Word-RAM model with $w \ge \log n$.

$^{**}$ Notice that this is consistent with practice. If you have any sense, you would set $b$ to be a power of two in an implementation.


Why can't we round results of linear programming to get integer programming? If linear programming suggests that we need $2.5$ trucks to deliver goods, why can't we round up and say $3$ trucks are needed?
If linear programming suggests we can afford only $3.7$ workers, then why can't we just round down to $3$ workers?

When can we not use this rounding technique?

In $\mathbb R$, one can simply round down or round up to obtain an element of $\mathbb Z$. Only two choices!

However, in $\mathbb R^n$, one has $2^n$ ways of rounding to obtain an element of the integer lattice $\mathbb Z^n$. For example, if $n=100$, one has $2^{100} \approx 10^{30}$ possible ways of rounding.

Of course, one can round all entries of an $n$-dimensional vector down or up, but do note that the Euclidean distance between the two farthest vertices of the hypercube $[0,1]^n$ is $\sqrt n$. If $n=100$, then $\sqrt{100} = 10$.

Unfortunately, to the best of my knowledge, there is no guarantee that the solution to the integer program will be found via one of the $2^n$ possible rounding schemes.

Fortunately, some linear programs have integer solutions and, thus, no rounding is required.


Understanding an algorithm for the gas station problem In the gas station problem we are given $n$ cities $\{ 0, \ldots, n-1 \}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. Our goal is to go from a source to a destination in the cheapest possible way. Our tank is limited by some value.

I try to understand the algorithm, so I manually wrote down steps to calculate the solution. Unfortunately I got stuck - at some point there are no edges to consider, I don't know why, maybe I'm missing something.

Example:
road:
0 ----------- 1 ------------ 2 -------------- 3
(it doesn't have to be that simple, it could be any graph i.e. there could be roads between 0->2, 0->3, 1->3 etc.)

Source: 0, Destination: 3, Tank: 10 units
Fuel prices: 0: 10 units, 1: 10 units, 2: 20 units, 3: 12 units
Lengths: 0->1: 9 units, 1->2: 1 unit, 2->3: 7 units
Optimal solution: fill 9 units at 0 and 8 units at 1. Total cost then is 170 units (9 * 10 + 8 * 10).

So I tried to calculate it as shown here (paragraph 2.2)

GV[u] is defined as:
GV[u] = { TankCapacity - length[w][u] | w in Cities and fuelPrice[w] < fuelPrice[v] and length[w][u] <= TankCapacity } U {0}

so in my case:
GV[0] = {0}
GV[1] = {0}
GV[2] = {0, 3, 9}
GV[3] = {0}

D(u,g) - minimum cost to get from u to t starting with g units of fuel in tank:
D(t,0) = 0, otherwise:
D(u,g) = min (foreach length[u][v] <= TankCapacity)
         {
           D(v,0) + (length[u][v] - g) * fuelPrice[u]                             : if  fuelPrice[v] <= fuelPrice[u] and g <= length[u][v]
           D(v, TankCapacity - length[u][v]) + (TankCapacity - g) * fuelPrice[u]  : if  fuelPrice[v] > fuelPrice[u]
         }

so in my case:
D(0,0) = min { D(1,0) + 9*10 }  - D(0,0) should contain minimum cost from 0->3
D(1,0) = min { D(2,9) + 10*10 } - in OPT we should tank here only 8 units :(
D(2,9) = min { ??? - no edges which follows the condition from the reccurence

Nevertheless D(0,0) = 90 + 100 + smth, so it's already too much.

To achieve the optimal solution algorithm should calculate D(2,7) because the optimal route is:
(0,0) -> (1,0) -> (2, 7) -> (3, 0) [(v, g): v - city, g - fuel in tank].
If we look at G[2] there is no "7", so algorithm doesn't even assume to calculate D(2,7),
so how can it return optimal solutions?

Recurrence from the document doesn't seem to work or what's more likely I do something wrong.

Could anybody help me with this?

The problem is in the condition for the first argument to min() in Equation (4) on p. 7.  It's currently

c(v) <= c(u) and g < d[u][v]

but it should be

(c(v) <= c(u) or v = t) and g < d[u][v]

to force arrival at t to have no gas left.  (Just as with my explanation below for the bug in Fill-Row(u, q), we are never interested in the cost of gas at t.  And as with there, another way to fix the problem would be to overwrite c(t) with 0 at the start of the algorithm.)

Fixing this mistake (in the published algorithm), combined with adding in the missing edges as I describe below (your mistake :-P), should be enough to get everything working.

One thing you're missing is that the graph G must be complete (first sentence of section 2, p. 4) -- and if it's not complete, any missing edges must be added, with the weights found by taking minimum path lengths in the graph.  So e.g. in your example graph, there should be (among others) an edge from 1 to 3 with weight 8 (corresponding to the path via 2), so that in fact GV[3] = { 0, 2 }.

I'm not sure whether that will completely solve the problem for you, but it should help.

Separately, I think there's a bug in the Fill-Row(u, q) algorithm on p. 6: this algorithm should treat the case q=1 specially, but it doesn't.  I believe it could be fixed by changing

if c(v) <= c(u)

on line 3 to

if c(v) <= c(u) or q = 1

to force any final leg to arrive at the destination empty.  (Intuitively, we should always disregard the price of gas at the final destination, t.)  Another way around this would be to overwrite c(t) with 0 at the outset.


A Graph's Density and Sparsity A graph is dense when |E| (edges) is closest to $|V|^2$.
A graph is sparse when |E| is closer to $|V|$.

What does it mean to take the magnitude of the vertices? Secondly, I am having a hard time conceptualizing why the above two rules are true.

Also can someone elaborate on why if a graph is sparse, it should be represented with an adj list and why if it is dense, it is best to use an adjacency matrix instead?

The notation $|V|$ here means the number of vertices in your graph. Likewise, $|E|$ is used to denote the number of edges. We typically say that a graph is sparse whenever $|E| \in O(|V|)$ - i.e there are few enough edges. Similarly, we say that a graph is dense whenever $|E| \in \Theta(|V|^2)$ - i.e there are many edges in your graph. These are not really rules, but rather just the terminology one often uses in textbooks.

An adjacency matrix requires $\Theta(|V|^2)$ space to store, while an adjacency list requires $\Theta(|V| + |E|)$ space to store. So when the graph is sparse, using an adjacency matrix is wasteful in terms of space usage, even though answering queries may be faster. On the other hand, is the graph is dense, then both representations require a quadratic amount of space to store, and so you are better off using the adjacency matrix for $O(1)$ edge queries. There are other trade-offs that one can consider as well depending on the queries you anticipate using often, such as vertex insertion/deletion, neighborhood queries, among others... but this is the general rule of thumb.

It may also make a difference when implementing certain algorithms, like Dijkstra's. Using an adjacency matrix, the algorithm takes $O(|V|^2)$ time, but using an adjacency list, it can be implemented in $O(|V| + |E| \log |E|)$ time. This type of trade-off is common when implementing different graph algorithms.


Would incrementing the min cut edges by 1 increase the max flow by 1 as well? Given the theorem that max flow <= min cut,
Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

Given the theorem that max flow = min cut, that would indeed be the case (if all capacities are integers).

If you make all min-cuts larger. There may be more than one.

To be clear: if you increase the capacity of all edges in all min-cuts, the max-flow may increase by more than one. At least one (assuming integer capacities), but then yet another cut may be minimal.

If you increase the capacity of each min-cut by one, the max-flow increases by one (again assuming integer capacities).


Particular function communication complexity computation Consider a boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with every $0/1$ vector of hamming weight $1$, then communication complexity of function is $\Omega(n)$. This is claim $4.23$ in Jukna's book. If $f$ satisfies $f(\bar{0})=0$ where $\bar{0}$ is vector of $0$, $f(x)=1$ with atleast $r$ number of $n$ of $0/1$ vectors $x$ each of Hamming weight $1$, then is communication complexity of function $\Omega(r)$? Could this possibly have truth?

There is a cheap lower bound of $\Omega(r)$ obtained by reduction. Suppose for simplicity that the $r$ dIstinguished coordinates are the first $r$. Let $g(x_1,\ldots,x_r) = f(x_1,\ldots,x_r,0,\ldots,0)$. Your condition on $f$ implies that $g$ satisfies Jukna's condition on $g$, so $g$ has communication complexity $\Omega(r)$. Any protocol for $f$ also works for $g$, so we get a lower bound of $\Omega(r)$ for $f$.


Complexity calculation of a recursive function with additional O(n) complexity There is a method that I want to calculate its complexity in asymptotic notation. It calls additional methods(equals and substring) which complexity is $O(n)$. If it was $O(1)$, I could figure out complexity of the calling method. I have tried some operations; however, I'm stuck on calculation with the additional part. Can you solve its complexity with steps?

public static int func(String x)
   if(x == null || x.equals(""))
      return 0;
   else
      return 1 + func(x.substring(1));

The question is absolutely not answerable without knowing what aFunctionWhichComplexityisO(n) returns.

Assuming that the function takes x as an argument, it might for example check if x contains the decimal representation of an integer y, and returns a string with the decimal representation of y-1 if y > 0, and null if y ≤ 0 or x does not contain the decimal representation of an integer.

In that case if x contains n characters, the time is $O (n·10^n)$.

Or the function always returns null, then the time is $O (n)$.


Why can't hash tables provide O(n) sorting? Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then retrieving them in order?

You just insert each number into the hash table, and remember the lowest and highest number inserted. Then for each number in that range, in order, test if it is present in the hash table.

If the array being sorted contains no gaps between values (i.e. it can be [1,3,2] but NOT [1,3,4]), this should give you O(N) time complexity.

Is this correct? I don't think I've ever heard of hash tables being used this way - am I missing something? Or are the restrictions (numeric array with no gaps) too much for it to be practically useful?

The reason you've never heard of hash tables being used like this is that hash tables are either "too much" or "not enough" in this situation.

If the range of elements being sorted is small, then you can use counting sort, or something similar.  But for counting sort, you would almost certainly want to use a simple array rather than a hash table.  If you know the max and min values of the numbers, then the array can be of size max-min+1, and value x would be associated with index x-min.  By using an array, you avoid the extra complications of hash tables.  Those extra complications are buying you nothing in this application, so hash tables are "too much".

Notice that your "no gaps" restriction ensures that the range of numbers is small (no larger than the number of elements in your original input).
However, if gaps can be present then the range of elements is potentially MUCH larger than the number of elements in your original input.  Then your running time is dominated by the size of that range, NOT by the size of your original input.  Hash tables do not help you deal with those gaps efficiently, so in this case hash tables are "not enough".


Is {a^n: n is a product of exactly two primes} regular? I am struggling to prove the following question.

  $L_1 = \{a^n: n \text{ is a product of exactly two primes}\}$

I feel like the language is not regular but I am having trouble proving it. I tried using pumping lemma but got stuck at the end. Here's how I did it:

Assume that the language is regular and $m$ is a constant of Pumping Lemma. Now let $w = a^M$ where $M > m$ and $M$ is a co-prime number. Clearly $w$ is in the language and $|w| > m$.

Now let $y=a^j$ where $j$ is between $1$ and $m$, with $|xy| \leq m$ and $|y| \geq 1$.

This is where I am getting stuck.
I feel like we should pump up but I don't know by "how much". Also, I feel like I have to know what is the next co-prime number after $M$, but can't figure it out.

Just pump up $(M+1)$ $y$'s. Now you get $xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$. Since $M$ is a product of two primes, $M(j+1)$ is a product of at least 3 primes, so $a^{M(j+1)}\notin L_1$, which proves $L_1$ is not regular by the pumping lemma.


Properties of a term rewrite rule While doing some bibliography on term-rewriting, I often found these two properties to define a term rewrite rule (see for example here and this one):

  A term rewrite rule is a pair $\langle l,r\rangle$ of terms, written $l \rightarrow r$, such that

  1) $l$ is not a variable

  2) all variables in $r$ occur also in $l$.

I fail to understand the reason of these properties, at least for the definition of a rule (I can see why they would matter for termination or confluence proofs). Why a term rewriting system could not contain a rule such as $x \rightarrow x + 1 - 1$ or $x \rightarrow x + y - y$ ? Just to provide some context, I'm trying to use TRS in the context of obfuscation, where such rewritings have meaning.

Can someone explain why rules composing a TRS would need these properties?

In general, there is no obstacle to define a rewrite system as above, and a few sources do indeed require rules 1. and 2. only as additional hypotheses.

However the hypotheses are almost always necessary (but not sufficient!) for both termination and confluence, which is indeed the main object of study of rewriting as a field.

Perhaps it's useful to remind why this is the case:

Termination:

If $x\rightarrow t$ is allowed as a rule, then any term $u$ rewrites to $t[u/x]$. In particular, the system is non-terminating.
If $l\rightarrow r$ and $r$ contains a fresh variable $y$ not in $l$, then for example, $l\rightarrow r[l/y]$, and so the system is non-terminating.

Confluence:

Take $x \rightarrow f(x)$ and $g(a)\rightarrow b$. Then
$$ g(f(a))\leftarrow g(a)\rightarrow b$$
for instance, breaking confluence. In particular, you can "insert" an $f$ around any term you like, which makes confluence very hard to satisfy.
If there are constants $a$ and $b$, then given the rule $f(x)\rightarrow g(y)$, you get
$$ g(a)\leftarrow f(x)\rightarrow g(b)$$
again, breaking confluence.

Now every theorem involving either termination or confluence could be prefaced with "assuming 1. and 2. holds, ..." but it makes sense to restrict your attention to systems where the theorems aren't trivially false. I don't think anyone would be shocked by a paper which lifts these restrictions though, at least condition 2. (condition 1. really creates anarchy). Condition 2. is mostly about non-determinism, for which rewriting is a nice framework in general.

There are some systems in which free variables can appear in the RHS, but usually not any fresh variable $y$ is allowed: there are additional constraints which need to be satisfied, e.g.

$$f(x) \rightarrow  f(y)\ \mid\ 0\leq y < x $$

where $x$ and $y$ are allowed to be integers. These types of systems are called constraint rewriting systems and are extensively studied.


What is the signal going from the computer to the screen? Im sorry if it is a weird question, but I cant seem to find an answer for this. What does the signal going to the screen look like in more abstract sense? Does it code the values of each pixel in a huge matrix, is it a computational stream that instructs the screen what to present?

In other words, can I grab this signal by a "listening" device for example and deconstruct it with algorithms? Not just grab the signal and present it on another screen. For example, if it is a matrix of pixel values, then I can run face recognition algorithms for example, to see if the signal sent to the computer is a picture of face or not.

It might also depend on the type of screen? Say that it is a LCD screen.

edit: To elaborate, if I wanted to take the signal sent to the screen and scan it for text (NSA style), could I? If so, what should I know of the signal that Im collecting to actually do this?
Disclaimer: Im not interested in spying on anyone.

The memory you are asking about really exists and is called framebuffer. However, it's not easy to directly access this memory on modern computers, because it's intentionally hidden from user processes.

For more info - click here.


Is it possible to determine if C=A+B faster than adding A+B in logical circuits With an adder circuit where A+B=C, I am trying to have a method to determine when C will be valid based on a change in A or B.  I know that it is possible to just determine the longest the circuit would take, but is it possible to determine if the result (C) is equal to A+B.  This would speed up the result of the operation as if A and B had a small change, C could be determined faster than a full adder cycle.

In general:  If you know A, B, and C, can you determine if A+B=C faster than adding A+B

Consider computing $\overline{a_{n-1}\ldots a_0}+\overline{b_{n-1}\ldots b_0}=\overline{c_{n-1}\ldots c_0}$. If the last $(k+1)$-bits are correctly computed, then $c_{k+1}$ is correct if and only if
$$\big((a_k\wedge b_k)\vee((a_k\oplus b_k)\wedge \neg c_k)\big)\oplus a_{k+1}\oplus b_{k+1}=c_{k+1}.$$
That is because the first part, $(a_k\wedge b_k)\vee((a_k\oplus b_k)\wedge \neg c_k)$ indicates whether there is a carry-over. So you can check the correctness for each bit in parallel.

However, in theory both questions require $\Omega(\log n)$-depth bounded fan-in circuits. Good thing is, for the checking problem the $\log n$ part in the circuit depth is only for a $n$-bit $\textsf{AND}$, so I think it is a constant boost in the performance.


Is C actually Turing-complete? I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an actual implementation.)

The "obvious" answer (roughly: it can address an arbitrary amount of memory, so it can emulate a RAM machine, so it's Turing-complete) isn't actually correct, as far as I can tell, as although the C standard allows for size_t to be arbitrarily large, it must be fixed at some length, and no matter what length it is fixed at it is still finite. (In other words, although you could, given an arbitrary halting Turing machine, pick a length of size_t such that it will run "properly", there is no way to pick a length of size_t such that all halting Turing machines will run properly)

So: is C99 Turing-complete?

I'm not sure but I think the answer is no, for rather subtle reasons. I asked on Theoretical Computer Science a few years ago and didn't get an answer that goes beyond what I'll present here.

In most programming languages, you can simulate a Turing machine by:

simulating the finite automaton with a program that uses a finite amount of memory;
simulating the tape with a pair of linked lists of integers, representing the content of the tape before and after the current position. Moving the pointer means transferring the head of one of the lists onto the other list.

A concrete implementation running on a computer would run out of memory if the tape got too long, but an ideal implementation could execute the Turing machine program faithfully. This can be done with pen and paper, or by buying a computer with more memory, and a compiler targeting an architecture with more bits per word and so on if the program ever runs out of memory.

This doesn't work in C because it's impossible to have a linked list that can grow forever: there's always some limit on the number of nodes.

To explain why, I first need to explain what a C implementation is. C is actually a family of programming languages. The ISO C standard (more precisely, a specific version of this standard) defines (with the level of formality that English allows) the syntax and semantics a family of programming languages. C has a lot of undefined behavior and implementation-defined behavior. An “implementation” of C codifies all the implementation-defined behavior (the list of things to codify is in appendix J for C99). Each implementation of C is a separate programming language. Note that the meaning of the word “implementation” is a bit peculiar: what it really means is a language variant, there can be multiple different compiler programs that implement the same language variant.

In a given implementation of C, a byte has $2^{\texttt{CHAR_BIT}}$ possible values. All data can represented as an array of bytes: a type t has at most
$2^{\texttt{CHAR_BIT} \times \texttt{sizeof(t)}}$ possible values. This number varies in different implementations of C, but for a given implementation of C, it's a constant.

In particular, pointers can only take at most $2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$ values. This means that there is a finite maximum number of addressable objects.

The values of CHAR_BIT and sizeof(void*) are observable, so if you run out of memory, you can't just resume running your program with larger values for those parameters. You would be running the program under a different programming language — a different C implementation.

If programs in a language can only have a bounded number of states, then the programming language is no more expressive than finite automata. The fragment of C that's restricted to addressable storage only allows at most $n \times 2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$ program states where $n$ is the size of the abstract syntax tree of the program (representing the state of the control flow), therefore this program can be simulated by a finite automaton with that many states. If C is more expressive, it has to be through the use of other features.

C does not directly impose a maximum recursion depth. An implementation is allowed to have a maximum, but it's also allowed not to have one. But how do we communicate between a function call and its parent? Arguments are no good if they're addressable, because that would indirectly limit the depth of recursion: if you have a function int f(int x) { … f(…) …} then all the occurrences of x on active frames of f have their own address and so the number of nested calls is bounded by the number of possible addresses for x.

A C program can use non-addressable storage in the form of register variables. “Normal” implementations can only have a small, finite number of variables that don't have an address, but in theory an implementation could allow an unbounded amount of register storage. In such an implementation, you can make an unbounded amount of recursive calls to a function, as long as its argument are register. But since the arguments are register, you can't make a pointer to them, and so you need to copy their data around explicitly: you can only pass around a finite amount of data, not an arbitrary-sized data structure that's made of pointers.

With unbounded recursion depth, and the restriction that a function can only get data from its direct caller (register arguments) and return data to its direct caller (the function return value), you get the power of deterministic pushdown automata.

I can't find a way to go further.

(Of course you could make the program store the tape content externally, through file input/output functions. But then you wouldn't be asking whether C is Turing-complete, but whether C plus an infinite storage system is Turing-complete, to which the answer is a boring “yes”. You might as well define the storage to be a Turing oracle — call fopen("oracle", "r+"), fwrite the initial tape content to it and fread back the final tape content.)


Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$ Does there exist a Deterministic pushdown automata for the language $L=\{ a^ib^j| i \neq 2j+1, i,j>0\}$ where $\Sigma = \{a,b\}$
I have tried to find a pushdown automata and it turned out to be a non-deterministic one.

Yes, here the idea of one with three states. I don't know stuff formally enough to write tuples.

Keep track of the parity of 'a's you read in two states.
If you read 'aa', push A on the stack
When you hit b, you better be on odd parity
Pop 'A' for every 'b' you read
At the end of the input, succeed if the stack is exactly empty.

This accepts only when i == 2j+1. Then, invert the last step, while keeping the requirement to keep it in the format $\{a^ib^j\}$ to get the version below. This requires adding one more state.
This might be a valid formal version, or it might not:
state,      input (z=end-of-string),
               top of stack (E=empty, *=anything),
                  action
q_a_even,   a, *, do nothing and transition to q_a_odd
q_a_even,   b, *, transition to q_b_ok
q_a_even,   z, *, succeed
q_a_odd,    a, *, push 'A' and transition to q_a_even
q_a_odd,    b, E, transition to q_b_ok
q_a_odd,    b, A, pop and transition to q_b_danger
q_a_odd,    z, *, succeed
q_b_danger, a, *, fail
q_b_danger, b, E, succeed
q_b_danger, b, A, pop and transition to q_b_danger
q_b_danger, z, A, succeed
q_b_danger, z, E, fail
q_b_ok,     a, *, fail
q_b_ok,     b, *, transition to q_b_ok
q_b_ok,     z, *, succeed


What is the different between Dijsktra's algorithm and KNN? I am implementing machine learning software and in my case, I am using K-nearest neighbour classifier to get the task done.

So far, I am trying to understand how Dijkstra's algorithm that has been used to solve salesman travel problem is different from K-nearest neighbour algorithm?

What is the different between Dijsktra's algorithm and KNN?

Almost everything.

$k$ nearest neighbor is a classification algorithm. It stores a list of [(features1, label1), (features2, label2), ..., (features-n, label-n)]. When it gets a new item features it calculates the distance to each of the $n$ stored items. It finds the $k$ closest ones. It returns the label which is most often in those $k$ examples.

Dijkstras algorithm is a graph search algorithm. It takes a graph $G = (V, E)$, a start node $s \in V$ and a target node $t \in V$ as input and returns the shortest path (v_1, \dots, v_n) with $v_1, \dots, v_n \in V$ from $s$ to $t$.

(You might be interested in the label correction algorithm, a generalization of Dijkstras algorithm)

How they can be related. Somehow.

$k$ nearest neighbor can also operate on graphs. If you have a graph-like structure and your distance measure is e.g. the number of hops from a node, then you would use breadth first search.


Prove or disprove that DTIME(n^2)=NL I need to prove or disprove $DTIME(n^2)=NL$. It kind of feel obvious that I need to disprove it, because if I have non-deterministic machine $M$ that uses $\log n$ space, then it meets at most $|Q| n\log n\ 2^{\log n}=|Q|\log n \ n^2 = \omega(n^2)$ ($Q$ denotes the number of states) different configurations, which bounds the running time, therefore intuitively it looks like I'll need more then $n^2$ to run $M$.
Can someone explain to me how would you approach to these types of problems? Because I always find my self resorting to "trial and error" with diagonalization and padding arguements.
Thanks in advance.

Let's say that a class $\cal C$ is closed under "reverse quadratic padding" if for any language $L$, if $Q(L) = \{\langle |x|, 0^{|x|^2} \rangle : x \in L \}$ belongs to $\cal C$ then $L$ also belongs to $\cal C$.

The class $\mathsf{NL}$ is closed under reverse quadratic padding: if $Q(L) \in \mathsf{NL}$, then we can decide $L$ itself in $\mathsf{NL}$ by simulating the decider for $Q(L)$. For that we use our ability to count up to $n^2$ (here $n$ is the input length), noticing that $O(\log(n^2)) = O(\log n)$.

In contrast, the class $\mathsf{DTIME}(n^2)$ isn't closed under reverse quadratic padding. Indeed, use the time hierarchy theorem to find a language $L \in \mathsf{DTIME}(n^3) \setminus \mathsf{DTIME}(n^2)$. Then $Q(L) \in \mathsf{DTIME}(n^2)$, whereas $L \notin \mathsf{DTIME}(n^2)$.


Why is the PageRank vector also the eigenvector of the web adjacency matrix? From wikipedia:

  The PageRank values are the entries of the dominant eigenvector of the
  modified adjacency matrix. This makes PageRank a particularly elegant
  metric

Can anyone please elaborate on the connection between the eigenvector and the PR vector? Why are they related?

PageRank is the stationary probability (i.e. dominant eigenvector) of the following random walk: with probability 0.85, choose a random outgoing link; with probability 0.15, choose a random web page. The "modified adjacency matrix" that Wikipedia talks about is obtained from the actual adjacency matrix $A$ by computing $0.85 A + 0.15 J$, where $J$ is the all-ones matrix. See this talk (page 13).


non-binary self balancing tree I'm looking for a tree data structure that allows to keep the tree balanced in high (minimum high as possible).

I mean, suppose a tree where:

each node has a parameter k that is the maximum number of sons that can be attached to him, $0≤k≤N$
all the operations will be about insert and delete (no search): it's just just important that every node know the son/s, I'm not interested at all in search (<0.1% of operations)

Would an adaption of RB-tree or AVL tree be a good idea for that task or there are better solutions (other data structures, other kind of tree, etc)?

You can use a binary prefix-trie (critbit-tree). It's not exactly selfbalancing, but it never requires rebalancing and imbalance is limited. For example, with 64bit keys, the maximum depth is strictly 64. This is not exactly the lowest possible height, but maybe that requirement can be relaxed because no rebalancing ever occurs?

You can find an (my) implementation here.


Process state in multi threaded process What would be the process state in a multi threaded process, in which threads are in different states (running, waiting, blocked etc)

In short, the lifecycle of thread does not interfere with the lifecycle of a process.

Processes and threads have different execution cycles; threads will execute and die while their process will continue to run until it gets a exit, truncate or die call due to normal execution (or in case of deadlock handling).

If a process contains only one thread, then if the thread is running, the process is in its running state. Otherwise, it can go into ready, wait, or die.
If a process contains multiple threads, it will execute until all jobs are completed. If a thread goes inactive it will not end a process; a process may enter ready state or be in running state.


How does $n^c \lg n, 0<c<1$ compare to other common time complexities Between what two common time complexities would you place $n^c lg n, 0<c<1$?

The following table illustrates the common time complexities.
Source: wikipedia

$O(n^c \log n)$ is above $O(n^c)$ but below $O(n^{c+\varepsilon})$ for any $\varepsilon > 0$. This is true for any $c \geq 0$, including $c < 1$.

For example, $n^{0.5} \log n$ is not in $O(n^{0.5})$ but is in $O(n^{0.500001})$.

This is one of the reasons for the invention of the "soft O" notation $\tilde{O}(n^c)$, defined as the union of $O(n^c (\log n)^d)$ for all $d \geq 0$. Soft O allows you to fudge log factors and focus on the most important part, which is the highest-order polynomial exponent.


Is the difference of two context-free languages still context-free? i am asking myself the following question:

Assuming: A and B are context-free languages, then A - B (difference) must also be context-free language, right?
but I do not know how to prove it.

The complement of a context-free language $L$ is not necessarily context-free, but it is the difference between two context-free languages ($\Sigma^* - L$). (Here $\Sigma$ is the alphabet of $L$.)

See, for example, Is the complement of { ww | ... } context-free? for an example of a context-free language whose complement is not context-free.


Cycles in undirected graph: reducing to minimum I am working on the problem of finding cycles in an undirected graph.
I made up my solution by first detecting if any cycles are present with a DFS algorithms and detecting any backtracking, and second, recursively explore all the found backtracked edges until I find the starting vertex.
The problem I have is that this approach gives additional cycles, and I don't know how I can remove them in a post-processing step.

The classical way is to represent the cycles as binary vectors, and then XOR them by pairs: if the result is equal to another cycle, then the latter can be removed.

For example, consider the following graph, that obviously has only two basic cycles:

Exploring all possible cycles will give these 3:

c1: 1-2-3
c2: 2-3-4
c3: 1-2-4-3

Converting to binary vectors:

edge | c1   c2   c3
1-2  | 1    0    1
1-3  | 1    0    1
1-4  | 0    0    0
2-3  | 1    1    0
2-4  | 0    1    1
3-4  | 0    1    1

Computing $c1 \oplus c2$ will give 110011, which is equal to c3, so we can remove c3.

But in many situations, this is not enough.
For example, consider the following graph, having $v=4$ vertices and $e=6$ edges.

A well know result states that for a single-connected graph  with $v$ vertices and $e$ edges, the number of cycles will be $c=e-v+1$, so we have 6-4+1=3 cycles in this example.

But by proceeding with my approach, I get the following 4 cycles:

c1:   1-2-3
c2:   1-2-4
c3:   1-3-4
c4:   2-3-4

If I convert them to binary vectors and XOR them, I am not able to remove the additional cycle.

edge | c1  c2  c3  c4
1-2  | 1   1   0   0
1-3  | 1   0   1   0
1-4  | 0   1   1   0
2-3  | 1   0   0   1
2-4  | 0   1   0   1
3-4  | 0   0   1   1

$c1 \oplus c2 = 011110$
$c1 \oplus c3 = 101101$
$c1 \oplus c4 = 110011$
$c2 \oplus c3 = 110011$
$c2 \oplus c4 = 101101$
$c3 \oplus c4 = 011110$

All these computations produce binary vectors with 4 '1', while all the initial cycles have 3. Thus I can remove none.

Note that this not only a matter of a (single) one additional cycle. For more complex graph (say, Petersen graph for example), I get more than one additional cycles.

I am looking for any ideas on how to remove the additional cycles.

Edit: As suggested in answer, I have build the incidence matrices for the two examples above:

             A1                A2
vert:      1 2 3 4           1 2 3 4
       1 | 1 1 0 0 |     1 | 1 1 0 0 |
       2 | 0 1 1 0 |     2 | 0 1 1 0 |
edges: 3 | 1 0 1 0 |     3 | 1 0 1 0 |
       4 | 0 1 0 1 |     4 | 0 1 0 1 |
       5 | 0 0 1 1 |     5 | 0 0 1 1 |
                         6 | 1 0 0 1 |

Edit 2
For A2, I computed the Reduced Echelon Form (that I understand is useful to find the solutions to $AX=0$):

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

But this stills end up with a null vector...

Edit 3: I come back to this question as I still didn't get it.
The answer from @Yuval Filmus suggest to solve $A x = 0$ to find the cycle basis. But what exactly represents the different $x_i$ values?
Because if I make a parallel with linear algebra, then using the matrix $A2$, this would mean I need to solve this:

$
\begin{aligned}
x_1 + x_2 &= 0 \\
x_2 + x_3 &= 0 \\
x_1 + x_3 &= 0 \\
x_2 + x_4 &= 0 \\
x_3 + x_4 &= 0 \\
x_1 + x_4 &= 0 \\
\end{aligned}
$

Beside the fact that the solution to this is $\{0,0,0,0\}$, I don't understant what $x_i$ represents.

Consider the incidence matrix of your graph, which is the $E \times V$ matrix in which each row contains exactly two 1s, corresponding to the vertices constituting the given edge, and the rest of the entries are 0. We think of the entries as belonging to $\mathbb{Z}_2$. A set of edges is in the left kernel of the matrix iff it is an XOR of cycles; it is known as the cycle space of your graph. You can find a basis for the cycle basis by finding a basis for the left kernel (this is an exercise in linear algebra). The basis will contain $|E|-|V|+c$ elements, where $c$ is the number of connected components.

If you don't like XOR, you can instead orient your edges arbitrarily, and then use the orientation to form a matrix in which each row contains one $1$ entry and one $-1$ entry. The left kernel of the matrix over the integers is known as the integral cycle space (also described in the link above), and it consists of sums (with integer coefficients) of cycles, where now a cycle is a sum of edges, some of which are possibly negated so that the orientations match.


How to apply Arden's theory to determine a regular expression If $P=ab$ and $Q=a^*$,
how do I use Arden's theorem to determine the regular expression $R$.
I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. Also how would I use that to check that $R$ satisfies Arden's equation.

Arden's theorem states that $A^*\,B$ is the least fixed point of the equation:
$$ X = A\,X\,\cup B$$
and that $A\,B^*$ is the least fixed point of the equation:
$$X = X\,B\,\cup A$$
In your case, $R = Q\,P^* = a^* (a b)^*$.