Can we use domains other than the naturals in computability theory? I wonder why people assume the domain of a computable function is $\mathbb N$? For example, in Wikipedia.

Can its domain be any countable set rather than $\mathbb N$?

Can its domain be an uncountably infinite set?

The domain is finite strings of symbols from some alphabet – i.e., initial contents of Turing machine tapes. The natural numbers can be easily coded as finite strings: either in unary using length or in some higher base using symbols from the tape alphabet as digits. Other countable sets (e.g., integers and rationals) can be coded if, and only if, there is a computable bijection between that set and the naturals. However, you can't let your domain be any countable set: for example, if you want your domain to be the set of Turing machines that halt on every input, you couldn't even tell which Turing machine a given finite string codes.

There's no way to use an uncountable domain because the initial contents of the tape must be finite and there are only countably many finite strings over any finite alphabet.


Implicit Leading 1 in Binary Floating Point Is the convention of dropping the leading 1 when storing the significand a given in all binary floating point representations or not necessarily?

As @BugKiller says, if it is IEEE format, it doesn't matter how many bits (32, 64, 43, etc) uses your representation, you drop the leading 1. And I think is the same thing with subnormal numbers taking a leading 0. Other floating point representations not specified within IEEE takes the same idea, because this dropped 1 comes from binary representation as any non-zero number will have a leading one, you drop it and you gain 1 bit to expand your representation.


Is this restricted promise-3SAT version coNPComplete? Given a $3SAT$ problem the decision version of the problem (if it has a solution or not) is $NPComplete$. Now, given that we consider the promise version of the $3SAT$ problem, the promise is every $3SAT$ problem provided always has at least 1 solution.

Query: Does every solution of the above $3SAT$ problem instance have a particular property (one that can be tested in polynomial time. For eg: 'for any solution $A_i$, $N$ numbers immediately smaller than A are co-prime' or something similar; where $N$ is the input length)?

The problem and property can be encoded as a pair consisting of $3SAT$, and another $N$ input circuit of polynomial size ($N^c$ for some constant $c$)

This promise version is definitely in $co-NP$ (as if there is a solution that does not satisfy the given property, that solution is the $co-NP$ certifcate of polynomial length).

Is this problem also $co-NPComplete$ (as it still involves getting the failing solution first)?

Your problem is coNP-complete when the property is "all variables are zero". Given a SAT formula $\varphi$ on $x_1,\ldots,x_n$, construct a new SAT formula $\psi$ by replacing each clause $C$ of $\varphi$ with $\lnot y \lor C$ (where $y$ is a new variable), and adding clauses $y \lor \lnot x_i$ for $1 \leq i \leq n$. The satisfying assignments of $\psi$ are obtained from those of $\psi$ by setting $y = 1$, and there is an additional satisfying assignment in which all variables are zero. Hence $\varphi$ is satisfiable iff not all satisfying assignments of $\psi$ satisfy the property.


Algorithms for almost sorting I want to find a comparison sorting algorithm that can almost sort a set of data, using the least comparisons possible.
What I mean by "almost" is that if the perfectly sorted data is $[x_1, x_2, …, x_n]$ and the almost sorted data is $[x_{i_1}, x_{i_2}, …, x_{i_n}]$, then $\forall j \in [\![1, n]\!], |i_j - j| \leq C$, $C$ being a parameter of the algorithm.
I want to emphasize that I want to minimize the number of comparisons. Other operations don't matter in the complexity. I would like to know if a number of comparisons next to $\frac{n\log_2 n}{C}$ can be possible.
In practice, I have to work with $n \simeq 1000$ and $C \simeq 10$ and only the comparisons are done by a human.
Are there any algorithm of the kind? Could I have some insight about it? Thanks.
EDIT: I got two ideas to almost sort:

The first one is to quicksort the array, and stop when I have to sort a sub-array of $\leq C$ data. The best case scenario requires roughly $\sum\limits_{k=0}^{\log_2(n/C)}2^k\frac{n}{2^k} = n\log_2(n/C)$ comparisons.
The algorithm is correct because sub-arrays are relatively sorted, and since they are of size $\leq C$, a value can't be farther than $C$ from its sorted position. The problem is that the worst case scenario is still in $\Omega(n^2)$ ;
The second idea is to sort using an insertion sort with a dichotomic search, and stop the search when the bounds of the search are distant of at most $C$. With this method, I get roughly $\sum\limits_{k=1}^{n-1}\log_2(k/C) = \log_2((n-1)!) - n\log_2(C)\simeq n\log_2(n/C) - n$ in the worst case, which is better than the previous algorithm, but I am not quite sure that the array will be $C$-almost sorted.

EDIT 2: I found that the second algorithm is not correct. If, during the first insertion, $x_n$ is put before $x_1$, then their relative order will not change during the rest of the execution, therefore one of them will be farther than $C$ from its sorted index if $n > 2C$.

Call an array $C$-sorted if each element is at-most $C$ places away from its place had the array been sorted (this is the same as "almost"-sorted array in the question, but in plain English).
Assume we will use comparison sort.
Claim One: Given an array of $n$ elements that is $C$-sorted,  we can sort it with at most $n\lceil\log_2 (C+1)\rceil$ comparisons.
Proof: Here is how we can sort the given array.

Create a buffer that is an array of size $C+1$.

One by one move the first $\min(n, C+1)$ elements to the buffer, keeping the buffer sorted using binary search to find the right place for each new element.

One by one move the min element from the buffer array to the result array, and, if the given array is not empty yet, add the next element to the buffer, keeping the buffer sorted using binary search to find the right place for that next element.

For each element in the array, at most $\lceil\log_2 (C+1)\rceil$ comparisons is used to find its right place in the buffer. The number of total comparisons used is at most $n\lceil\log_2 (C+1)\rceil$.  $\quad\checkmark$

Claim Two: At least $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil$ comparisons are needed to $C$-sort an array of size $n$ in the worst case.
Proof: Otherwise, suppose there is an algorithm that can $C$-sort any given array of size $n$ with less than $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil$ comparisons. Extending that algorithm with the algorithm shown in the proof of claim one, we obtain an algorithm that can sort any given array of size $n$ with less than $\log_2(n!)$ comparisons. That is well-known to be impossible. $\quad\checkmark$

Claim Three: There is no algorithm that can $C$-sort an array of size $n$ with $O(\frac{n\log_2 n}{C})$ comparisons.
Proof: We have, if $n\ge C^{1+\epsilon}$ for some fixed $\epsilon\gt0$,
$$\begin{aligned}\lim_{C\to\infty} \frac{\log_2 (n!) - n\lceil\log_2 (C+1)\rceil}{\frac{n\log_2 n}{C}} &= \lim_{C\to\infty} C\left(\frac{\log_2 (n!)}{n\log_2 n}-\frac{\lceil\log_2 (C+1)\rceil}{\log_2 n}\right)\\&\ge \lim_{C\to\infty} C\left(1-\frac1{1+\epsilon}\right)=\infty.
\end{aligned}\quad\checkmark$$

Indeed, $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil$ given a pretty strong lower bound for the number of comparison needed in the worst case since
$\log_2 (n!)$ is the lower bound to ordinarily sort an array, and, as $\log_2(n!)\approx n\log n$, for any fixed $C$,
$$n\lceil\log_2 (C+1)\rceil = o(\log_2 (n!)).  \ \ \color{#d0d0d0}{\text{(small o, not big O!)}}$$
That is, at least $(1-\epsilon)\log_2(n!)$ comparison is needed to $C$-sort array when $n$ is sufficiently large, for all fixed $\epsilon\gt0$ and $C$.

We also note that

on average, quicksort performs only about 39% worse than in its best case. In this sense, it is closer to the best case than the worst case. A comparison sort cannot use less than $\log_2(n!)$ comparisons on average to sort $n$ items (as explained in the article Comparison sort) and in case of large $n$, Stirling's approximation yields $log_2(n!) \approx n(\log_2 n − log_2 e)$, so quicksort is not much worse than an ideal comparison sort.

Now let us have an array of $n=1000$ elements and $C=10$.

Quicksort will perform about $2n\log n\approx 19931$ comparisons on average to sort the array, as shown on Wikipedia.
Claim Two says $\log_2 (n!) - n\lceil\log_2 (C+1)\rceil\approx4529$ are needed to $10$-sort the array in the worse case, which is sort of information-theoretical the best.
Note that $\frac{n\log_2 n}{C}\approx997$, which is much less than
of 4529.

So I believe, (some more argument are omitted here), an algorithm that performs about $n\log_2(n/C)\approx6643$ comparisons to $10$-sort the array is pretty much about the best we can get.


How is this expression a valid lambda expression? Can you explain how this expression follows the grammar of the lambda calculus?

$$\lambda x.x((\lambda y.yy)x)x = λx.x(xx)x$$

I am not sure why we have the parentheses following the $.x$ (on both sides of the equation).

When in doubt, write down a lot of parentheses:
$$\lambda x . ((x ((\lambda y . ((y y) x)) x)) x)$$
and
$$\lambda x . ((x (x x)) x)$$
In $\lambda$-calculus there is the convention that $A B C$ is understood to be $(A B) C$, that is, application associates to the left. So, if somebody wants to $A (B C)$ instead, they have to put in some parentheses.


Give one example where it takes Non- deterministically exponential time to solve the problem? I am a starter in complexity theory though I have fair knowledge in Turing machine. I know what it means to be non-deterministically polynomial time solvable but I am trying to understand where the time goes beyond polynomial time even using non-deterministic concept. Is it possible or we can do everything in polynomial time using non-deterministic concept though in reality it can not be implemented. Therefore, I am looking for an example where we can't do it in polynomial time rather it takes exponential time even after using non-deterministic concept. Please explain clearly why it takes exponential time(non-deterministically).

There are problems that cannot be solved in polynomial time on a nondeterministic machine. Indeed, there are problems that cannot be solved on any Turing machine, such as the halting problem.

We know from the nondeterministic version of the time hierarchy theorem that there are things that can be done in exponential time on a nondeterministic TM that cannot be done in polynomial time.  That is, $\mathrm{NP}\subsetneq\mathrm{NEXP}$.

Wikipedia gives several examples of $\mathrm{NEXP}$-complete problems: these are examples of problems that are provably not in $\mathrm{NP}$.


Optimality of A* search I use the A* search algorithm to to search for the shortest path from S to G.
The evaluation function is $f(n) = g(n) + h(n)$.

Since node A and B have the same estimated total cost, I choose to go node A.Then, the $f(n)$ of B is 8, C is 7, G is 10. After expanding C, $f(n)$ of G is 7. Therefore, the path is S-A-C-G with total cost 7.

However, there is a lower cost path S-B-G with $f(n) = 6$.
Is the path S-A-C-G still optimal or I did the search in the wrong way?

The A* algorithm requires that its heuristic function $h(n)$ is admissible for all $n$, meaning that it should never overestimate the (unknown) true cost from a node to the goal. This assumption appears to be violated in your example for nodes $S$, $A$, and $B$. Only for $n = C$ and $n = G$ is the heuristic function $h(n)$ admissible, but it should be for all nodes.

This is why the algorithm seems to be resulting in suboptimal paths for you.

A good example of an admissible heuristic function in 2D environments is often the Euclidean distance (straight-line distance). Unless you start involving strange things such as teleportation, this heuristic is always admissible (you can never get anywhere faster than by following a straight line). Although in your drawing, it seems like this wouldn't work. It doesn't look like your drawing was drawn "correctly". Some short paths seem to have higher costs than longer paths (visually).


Group tuples to satisfy constraints This is a problem that involves matching students with various skills into groups so that there are as many groups as possible while ensuring that each group has certain skills present. I've reduced it to this:

Given a set of $N$ people with $S$ skills where $A_{n,s}$ is the quantity of skill $s$ that person $n$ has.
Group the $N$ people into as many groups as possible, such that there are no more than $G$ people in any group, and so that the sum of each skill in each group is at least $B_s$.

Constraints: $N, S, G < 100$ and $A_{n,s}, B_s < 10$

I haven't been able to come up with a better solution that a brute force so far. Would be very keep for some pointers as to what I should be searching for to find an algorithm for this class of problem.

I suggest expressing this as an instance of integer linear programming (ILP).  Express boolean logic operations in zero-one integer linear programming (ILP) might be useful to you in figuring out how to do that.

In particular, introduce zero-or-one variables $x_{n,j}$, which is one if person $n$ is placed into group $j$, or zero otherwise.  You can now express each of your requirements as a linear inequality,  and then use an ILP solver to test for feasibility. Now do binary search (or simple iterative search) over the number of groups, to find the maximum number of groups for which you can find a feasible solution.


Bytes from integer using bitwise operators So I am extremely confused with using bitwise shifts used to extract the bytes from an integer. I find that if I do something like this...

int i = 512;
i & 0xFF; // this gives me the first byte

That must mean i & 0xFF gives me the first byte that is stored in memory. In other words, i & 0xFF is the first of the four bytes i consists of stored at the lowest memory address. Next, I think that i << 8 & 0xFF will then shift everything left by 8 bits and giving me the second byte. However, it is actually the opposite and only i >> 8 & 0xFF gives me the next byte. I do not understand why this is true. To me, it makes the most sense to left shift to get the next byte so why do I need to right shift by 8 to get the proceeding byte?

Contrary to what you think, extracing bytes by shifting and masking is completely unrelated to the storage order (both little-endian and big-endian storage schemes exist and don't influence the results).

An int variable is represented by 32 bits. The least significant byte is made of the eight least significant bits and you obtain them by

i & 0xFF
0b 111111111 0101010 01010101 000000000 => 0b 00000000 00000000 00000000 00000000

The neighboring byte is made of the eight neighboring bits; you discard the eight least significant bits by shifting (>>), then mask out:

(i >> 8) & 0xFF
0b 11111111 10101010 01010101 000000000 => 0b 00000000 00000000 00000000 01010101

And similarly for the remaining two bytes, with shifts of 16 and 24 (most significant byte).

Notice that I cared not to use the terms left/right and first/last, which are meaningless as they refer to some graphical representation or memory storage order. In the examples, the numbers are understood as binary numbers written with lsb on the right (and spacers for clarity), which is the most common convention.


Example of a language that is neither recognizable nor co-recognizable? Is there an example of a language that is neither recognizable nor co-recognizable?

A relevant (easy) theorem is that a language is decidable iff it is recognizable and co-recognizable.

An example of an undecidable language is the set "acceptance problem," i.e. the set of strings (Turing Machine = M, string = s) such that M accepts s. It is recognizable and not co-recognizable.

A less "constructive" proof that there exist unrecognizable languages is that there are uncountably many languages and countably many TMs. I believe this also establishes the existence of languages that are not recognizable or co-recognizable.

Is there an "example" of such a language?

I put "constructive" and "example" in quotes because I suspect I am creating a meta-logical contradiction, whereby stripping a language of recognizability and co-recognizability also strips it of the forms of describability that might intuitively constitute a "construction" or "description." I am interested in any results that make rigorous how to "talk" about languages that are not recognizable or co-recognizable, or any hardness results on doing so.

The language TOT of all Turing machines halting on all inputs is $\Pi_2$-complete, and so is neither recognizable nor co-recognizable. You can find more examples if you search for material on the arithmetical hierarchy. Anything beyond $\Sigma_1$ and $\Pi_1$ will fit your bill.


Finding longest balanced parentheses using $n$ smaller strings Given $n$ strings consisting only of '$($' and '$)$', how one can compute the length of the longest string that can be built by concatenating a subset of these strings in some order such that the resulting string is a balanced parenthesis?

Example: If we have the strings $\{"(()",")(",")","(("\}$, one can build the string $"(())()"$ which has length 6.  We cannot construct a longer one from the previous set, thus the answer is 6.

In general, the answer is always even, and always $\geq 0$ because we can always take the empty set.

Problem source: North American Invitational Programming Contest (NAPIC) 2017, Problem A.

First, let's remark that the order in which you put the selected strings is not significant as long as it is valid.  That means that you can put the strings in a canonical order and you know that the solution is a subsequence of that sequence.  The canonical order I suggest is first the strings which increase the number of opened parenthesis (with D.W. triplet notation, the triplets $\langle i,j,\ell \rangle$ for which $j>i$) tied resolved by increasing $i$, then those which don't change the number of opened parenthesis ($i=j$) then those which decrease the number of opened parenthesis($i>j$) this time solving the tie by decreasing $i$.

Then you apply the favorite technique of programming contests: dynamic programming. You are filling an array of $n$ columns.  An entry $c,r$ of $\ell$ states that with the $c$ first strings in our canonical order, you can have $r$ opened parenthesis pending with a total length of $\ell$.  This is filled using the content of the column $c-1$ with the initial column stating that with no strings you have a $0$ opened parenthesis pending and a length of $0$.  You have to pay attention to avoid entries which would need to have more opened parenthesis than available, and when an entry is reachable with two lengths to keep the longest one.

You avoid the  exponential behavior because you know that the strings have a bounded length of 300 (thus you can't have more than $300\; c$ opened parenthesis after $c$ columns instead of the $2^c$ entries which would have been possible without that bound)  and thus you are sure that after the ninth or so column, you'll have duplicate entries.


What's the purpose of ANDing a bit mask with all bits set to a value? I'm adapting an algorithm for calculating a CRC 16-bit CCITT (XModem) value from an ASCII input.  I've found some code here. I'm using the function the poster has in his question, but I've noticed at the bottom he does this:

calcrc = crc And &HFFFF

What's the purpose of applying such a bit mask that is all 1s to a value?  Doesn't that just return the value again?

The reason is crc that it's calculating is defined to be a 16-bit value, the And &HFFFF will truncate the most significant bit outside the 16-bit range if there is any overflow during the calculation.


Loopless NFA equivalent in strength to NFA For every nondeterministic finite state automata (NFA) that has self-loop(s), there exists an equivalent NFA that does not have any self-loop.

How do I prove this?

Make two copies of your original NFA and connect them in an appropriate way.


Some questions regarding an approximation algorithm for Cardinality Maximum Cut Problem in Vazirani's textbook! In Vazrani's textbook, page 22, the following exercise:

  2.1 Given a n undirected graph G=(V,E), the cardinality maximum cut problem asks for a partition of V into sets S and G\S so that the number of edges running between these sets is maximized. Consider the following greedy algorithm for this problem. Here $v_1$ and $v_2$ are arbitrary vertices in G, and for $A \subset V$, $d(v,A)$ denotes the number of edges running between vertex v and set A.

  Show that this is a factor 1/2 approximation algorithm and give a tight example. What is the upper bound on OPT that you are using? Give examples of graphs for which this upper bound is as bad as twice OPT.

First: the upper bound on OPT is easily the number of edges.
Second: I have an example of graph that shows that we have 3/5 (so close to 1/2 but not exactly) I tired for several days to find 1/2 but no sign to find one. Now, can I use the limit to show that we have 1/2. i.e. lim as m goes to infinity, $\frac{m/2 + 1}{m} = \frac{m+2}{2m}=1/2$ Is this correct?!! if not, then why!
Third: I want to understand the different between "Give examples of graphs to show that this upper bound is as bad as twice OPT" and "tight example"! I mean Are they the same thing?!! For example: tight example would show an approximation ratio 1/2 for this algorithm while "Give examples of graphs to show that this upper bound is as bad as twice OPT" would give 1/2 approximation ratio for this algorithm. Also it seems from the context of the question that "upper bound" we use is not good! do you know any other better upper bound than the number of edges to give a better bound!!

I'm here not to ask for solving problem, instead I just want to understand what the question wants exactly and different between some parts of this question.

Thank you!

An $\alpha$-approximation algorithm $A$ for a maximization problem is an algorithm which on instance $x$ produces a solution $y = A(x)$ of value $V(y) \geq \alpha OPT(x)$, where $V(y)$ is the value of $y$ and $OPT(x)$ is the value of the optimal solution.

A tight instance for such an algorithm is an instance $x$ such that $V(A(x)) = \alpha OPT(x)$. This instance shows that $A$ isn't a $\beta$-approximation algorithm for any $\beta < \alpha$.

In some cases it is impossible to find a single tight instance, yet it is still possible to show that the algorithm isn't a $\beta$-approximation algorithm for any $\beta < \alpha$ using a sequence of solutions $x_i$ satisfying $V(A(x_i))/OPT(x_i) \longrightarrow \alpha$. Such a sequence is sometimes also called a tight instance, even though in reality it is a sequence of instances rather than a single instance.

You are also wondering what is the correct answer to the question about which upper bound you are using. Your algorithm presumably uses the trivial upper bound, which is the total number of edges. If you find an "integrality gap" instance in which the ratio between this upper bound and the maximum cut is $\alpha$, then this means that any algorithm using this upper bound cannot have an approximation ratio better than $\alpha$. In your case you can take a large clique, for example (this is actually a sequence of bad instances).

The famous Goemans–Williamson algorithm uses a better upper bound, namely the value of a semidefinite relaxation of maximum cut. Using this better upper bound, it manages to increase the approximation ratio from 1/2 to roughly 0.878, which is conjectured to be optimal.


Can you share some pointers to get better at working alone in projects? I am an ML Engineer who works alone in projects most of the time. I don't have people who are much smarter than me working alongside.

Most of the time, I feel that working alone is a tedious job,one may get stuck at a lot of problems. In such cases my only go to option is Google. What effective techniques you use while you work on a project alone, because at the moment googling feels like looking for a needle in haystack (80% of the stuff will be useless for you).

Apart from that, some answers you search for lead you to more questions related to stuff explained there and it becomes a vicious circle of googling things leading to frustration. (And most of the developers out there suggest the top down learning methodology, where you do a problem at first and then breaking down to solve it which ends up in above problem.)

So would you like to weigh in with your experiences, like what thinking style you adopt, what are effective search methodologies, good ways of breaking down the problem, here you get quick help apart from SO etc. It's good if you can link to books, resources etc as well.

ML is an extremely broad subject but generally it can be understood broadly as follows

you formalize the problem
you identify the domain of the problem
you identify candidate models to solve the problem
you evaluate the candidate models with data subsets
you select a model and try to fit your data
you deploy the model

You can think of it as a(n iterative deepening ) search of a tree of choices.  To improve your odds of success (find a choice that solves the problem) you need the tree narrow down as quickly as possible e.g. pruning bad choices.  This is only acquired through experience but having a broad understanding of models helps e.g by taking introductory courses.

Once you've narrowed down the types of models you want to apply.  You want to know if you have the expertise to apply them.  Given that this is a broad subject, you acquire expertise only in a limited set of models.  If the model that best fits your problem is not in your domain of expertise you either refer it someone with that expertise or reject that you can solve the problem in a limited amount of time e.g. due to the complexity of the tree of choices for a non-expert.

Within your model expertise you'd have acquired a set of techniques to determine that even when you have the right model, if you do not have sufficient data, or data with sufficient quality, or the necessary computation resources you may not be able to deploy your model.


Problem Solving in MapReduce Framework I am looking for good resources which have classified and solved typical large scale data processing in MapReduce framework (like graph algorithms, statistics, numerical algorithms ...). Any help is appreciated!

Mapreduce does not seem to have received significant academic attention and/or widespread enthusiasm nor does it seem to have yet been integrated into much of the large previously-existing literature and theory on parallelism. This is partly due to it being relatively new, but there may be other reasons.

One possible angle: this is apparently not widely acknowledged or recognized but MapReduce seems mainly oriented towards & optimized for what are known as embarrassingly parallel problems where the problem space can easily be partitioned into independent parts requiring virtually no intercommunication, i.e. the "map" step. (this is partly the basis of some criticism of the simplicity of the model as in the Wikipedia article.)

The "reduce" step is a communication-heavy step of merging/combining/aggregating the separate results into a combined structure. [1] are slides on the background & structure of typical embarrassingly parallel problems, which classic examples are:

image processing,
fractal calculations e.g. Mandelbrot set, and
Monte Carlo calculations.

Another angle is that MapReduce has some similarities to the "master-slave" design pattern where the "master" distributes jobs and also handles collecting the results, and some surveys on "master-slave" decomposition of parallel problems may be available.

Embarrassingly parallel problems are also naturally "finely granular" and Mapreduce seems especially suited to "fine-grained" parallelism problems (such that the "fine grains" can be highly distributed over many computing machines). "Fine-grained" parallelism is possibly not studied as much from an academic point of view because its intrinsically theoretically less problematic.

Another angle: it's similar to "Bulk Synchronous Parallel" [4]. The reduce step is similar to "barrier synchronization".

A survey from 2006 by academic parallelism experts [2] that was meant to be very comprehensive and forward-looking at the time identified 7 widespread "dwarves" or basic parallelism structures found in algorithms (Section 3.2). Conspicuously and surprisingly, none have a MapReduce-like structure; i.e. MapReduce type problems are absent from the survey (but note Monte Carlo methods are one of the "dwarves" and is again regarded as embarrassingly parallel).

This would also tend to support the view that MapReduce is a kind of "toy" parallelism model. However! that point is not meant to detract from its widespread usefulness in many applications. Particularly with parallelism there can be great value in simpler models that avoid complexity and thereby also various pitfalls.

[1] Embarrassingly parallel overview

[2] The landscape of parallel computing: the view from Berkeley

[3] Current parallel models for computation tcs.se

[4] Is the mapreduce framework a type of BSP tcs.se


If two languages are decidable, can one be mapping reducible to the other? If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?

That is false. Consider for example the alphabet $\Sigma = \{0,1\}$ and the two languages $A = \emptyset$ and $B = \Sigma^*$.
Clearly both $A$ and $B$ are decidable (by the trivial algorithms that always reject and always acccept, respectively) but it is false that $A \le_m B$.


Algorithm to split bipartite graph into subgraphs I'm looking for an algorithm to split a bipartite graph into subgraphs with a specific constraint.  I'm not sure if any existing algorithms solve my problem or not.

I have an undirected bipartite graph where the nodes are customers ($C$) and services ($S$).  I want to split this into several smaller subgraphs, limiting the amount of services in each subgraph to some maximum number $N$.  Unfortunately, looking for disconnected subgraphs is not sufficient because the graph connectivity is too high, so I think I will need to duplicate services.

Formally, I want a set of subgraphs such that:

Each customer $c \in C$ appears in exactly one subgraph
All edges appear in exactly one subgraph (the one in which their customer appears)
Each service $s \in S$ can appear in any number of subgraphs (it's okay to duplicate services to help the split)
Each subgraph should have at most $N$ services (where $N$ is a given constant that is guaranteed to be larger than the highest number of services connected to any single customer)
The subgraphs should have as many customers as possible (without this restriction, it's trivially solvable by putting each customer in their own subgraph with a copy of their services).  That can be a heuristic rather than formally proven.

Can anyone suggest an algorithm for doing this?  The number of nodes is not huge (roughly 1000 customers, 100 services, with each customer connecting to 5 or less services) so brute force approaches or those with bad big-O scaling may be suitable.

It smells like it might be NP-hard.

One plausible approach is to use a SAT solver or ILP solver.  Suppose you decide you want to have at most $m$ subgraphs.  Then you can have boolean variables $x_{i,k},y_{j,k}$ indicating that customer $i$ goes into subgraph $k$ and service $j$ goes into subgraph $k$.  You can obtain a bunch of constraints (clauses) based on your requirements and then ask the SAT solver or ILP solver to find a feasible solution.  The worst-case running time is exponential.  This might or might not work well enough in your situation.


Create a binary search tree from a sorted array: Space complexity reasoning Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'.

class TreeNode:
    def __init__(self, x):
        self.right = None
        self.left = None
        self.val = x

Here is the solution:

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """

        left = 0
        right = len(nums) - 1

        return Solution.recursive_insert(nums, left, right)

    @staticmethod
    def recursive_insert(nums, left, right):

        if left <= right:

            mid = (left + right)//2
            node = TreeNode(nums[mid])

            node.left = Solution.recursive_insert(nums, left, mid - 1)
            node.right = Solution.recursive_insert(nums, mid + 1, right)

            return node

example_insertion = Solution()
example_insertion.sortedArrayToBST([1, 2, 3, 4, 5, 6, 7, 8])

I understand proving the time complexity is $O(n)$ by using the following recurrence relation:

$$T(n) = 2T(n/2) + C$$

I have a question about the space complexity... Here is how I rationalize it. Please correct me if I'm wrong.

The code to insert the left and the right child involves simply performing a worst case binary search (until left becomes greater than right, or start becomes greater than end). The function call stack keeps getting re-used, but goes to a maximum of $O(\log n)$ (which happens to be the worst case space complexity of binary search when done recursively and not iteratively).

Is my reasoning correct?

I would say try to think about it more in the terms of data structures used directly in the calculation of the result. Typically you wouldn't consider the call stack because you could in theory rewrite you algorithm to be iterative and have no issues with the call stack. The call stack is only an issue when you reach the max recersion depth. It is also not considered when just analyzing algorithms.

Space complexity is constant or $O(1)$ because you can modify the tree in place.

Your answer about call stacks more so relates to the worst-case time complexity as this is directly related to number of function calls (or call stacks in your case). This is going to be $O(\text{height})$ of the tree which is at most $n$, so $O(n)$ in worst case, but $\Theta(\log(n))$ in average case. The time complexity can be improved to better than $O(n)$ if you keep your tree balanced after each insertion.


Balanced Binary Tree Can someone please explain to me how the Wikipedia example on the left for a balanced binary tree is correct?

  One common balanced tree structure is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1

For node ABCDE, isn't the height of left subtree 2 and the height of the right subtree 0, making the difference of height 2?

EDIT As David rightly pointed out:

  That page defined "balanced" immediately above the example you're asking about, and it defines balanced in a different way to you.

I thought that the example was using the definition that comes immediately after the example, which I have quoted above. Apologies for the confusion.

That Wikipedia article is using a different definition of "balanced":

  A balanced binary tree has the minimum possible height.

Therefore, since a perfect binary tree of height $d$ has $2^{d}-1$ nodes, if a tree has $n$ nodes, the minimum possible height for that tree is $\left \lceil \log_2n \right \rceil$, and the tree you mention does indeed satisfy that condition.

Observe that the usual definition of "balanced tree" is in an asymptotic setting, i.e. depth is $\mathcal{O}(\log n)$.


How is Pure Maths utilized in Computer Science research? How can People with a background in Mathematics pursue PhD in Computer Science"

Although I have a Postgraduate degree in Mathematics with basic programming knowledge,it sounded quite interesting how knowledge in Mathematics can help to solve Computer Science Research Problems.

Since this site is for researchers in Computer Science,Can someone kindly tell:

What type of problems can a Mathematics postgraduate take up in Computer Science?
What is the current scenario of research in Computer Science where Mathematicians like us can make a significant impact?
What are the other skills needed apart from a sound Programming knowlegde to work here?

Any links/references would suffice too.

I have done courses on Linear Algebra,Abstract Algebra,Functional Analysis,Topology,Number Theory and have enjoyed them.

I really dont know how to use the concepts learnt in these courses can be used to solve research questions on Computer Science.

If someone can kindly comment how concepts in the above Mathematical facts can be used to do research in CS,I can understand why a reputed instititution in our country is asking for postgraduate in Mathematics for a PhD in CS.

Let's do these in the order you listed. I will not be comprehensive, I will just try to impress you by pointing out cool applications of mathematics in CS. Others may know of even cooler applications.

Linear algebra is used to compute the Page rank of web pages, which is the basis of Google engine ordering pages from more relevant to less relevant.
Abstract algebra is used to model computational effects, such as exceptions, input/output, memory, parallel computation etc.
Functional analysis is used in the JPEG image format which uses Fourier analysis to achieve lossy compression.
Topology is used in domain theory to give mathematical models of programming languages. Algebraic topology is used in topological data analysis, and homotopy theory is used in homotopy type theory to study equivalence of datatypes (I am oversimplifying) and how to convert between them.
Number theory is used in cryptography to provide public key protocols, such as the RSA algorithm. These are used every time you buy anything on the Internet.

So, is that convincing enough?


What is the difference between these two Edit Distance Algorithm Edit Distance is very well known problem in computer science. Came up with following algorithm after reading through CLRS but it doesn't work. Check the working algorithm below, I couldn't find why first algorithm doesn't work while second one does.
  public int find (String word1, String word2, int i, int j, int count) {
    if (i >= word1.length()) return  count + word2.length() - j;
    if (j >= word2.length()) return  count + word1.length() - i;

    if (dp[i][j] != -1) return dp[i][j];

    if (word1.charAt(i) == word2.charAt(j)) {
        dp[i][j] = find(word1, word2, i+1, j+1, count);
    } else {
        int replace = find(word1, word2, i+1, j+1, count + 1);
        int delete = find(word1, word2, i+1, j, count + 1);
        int insert = find(word1, word2, i, j+1, count + 1);

        dp[i][j] = Math.min(replace, Math.min(delete, insert));
    }

    return dp[i][j];
}

Notice, how I'm passing the cost of edit in method argument. Now, the algorithm which works. Here I'm not passing the edit distance in the method parameter instead of I'm adding 1 to recursive method.
  public int find (String word1, String word2, int i, int j) {
    if (i >= word1.length()) return  word2.length() - j;
    if (j >= word2.length()) return  word1.length() - i;

    if (dp[i][j] != -1) return dp[i][j];

    if (word1.charAt(i) == word2.charAt(j)) {
        dp[i][j]  = find(word1, word2, i+1, j+1, count);
    } else {
        int replace = find(word1, word2, i+1, j+1, count + 1);
        int delete = find(word1, word2, i+1, j, count + 1);
        int insert = find(word1, word2, i, j+1, count + 1);

        dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));
    }

    return dp[i][j];
}

I'm not able to think why first algorithm fails. Appreciate, if you can point my error in understanding.

I'm going to assume by "doesn't work" you mean "gives the wrong answer".
In dynamic programming, every cell in the table is supposed to represent a solution to a subproblem. In the case of edit distance, the subproblem is

Let dp[i][j] be the distance between word1.substring(i) and word2.substring(j)

But in your code, the statement of the subproblem is ambiguous. The cell dp[i][j] contains something that depends on count, but which count? It might very well be that many different counts correspond to the same pair i,j, because you can get to it by different "routes". If that happens, your program will just use whatever count it encountered first, write the answer to the table and never revise it again. Therefore, if the first route you took is not the optimal one, then the result will be wrong.
Consider what happens when I give your program the words "WORD" and "SWORD". Which number will be in dp[3][4]? The correct program will write 0 into that cell, and eventually it will find a route that leads to the point 3,4 and has a cost of 1. Your program, on the other hand, will write the count of the first route it takes, which in this case will be  4. And even though it may later find a better route, it will still trust that 4, because that's what the table says.
In summary, you make a subproblem with the indices i,j depend on some other quantity, which violates the principles of dynamic programming. If your dp table had a third dimension, as in dp[i][j][count], then it might have worked, because then every subproblem would be fully specified.


How does 'deforestation' remove 'trees' from a program? I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function -- see this good answer on CodeReview here), but when I compared that with the wikipedia entry on the technique it talked about 'removing trees' from a program.

I understand how a program can be parsed into a syntactic parse tree (is that right?), but what is the meaning of this use of deforestation for some kind of simplification (is it?) of programs? And how would I do it to my code?

Yatima2975 seems to have covered your first two questions, I'll try to cover the third. To do this I'll treat an unrealistically simple case, but I'm sure you'll be able to imagine something more realistic.

Imagine you want to compute the depth of the full binary tree of order $n$. The type of (unlabeled) binary trees is (in Haskell syntax):

type Tree = Leaf | Node Tree Tree

Now the full tree of order $n$ is:

full : Int -> Tree
full n | n == 0 = Leaf
full n = Node (full (n-1)) (full (n-1))

And the depth of a tree is computed by

depth : Tree -> Int
depth Leaf = 0
depth (Node t1 t2) = 1 + max (depth t1) (depth t2)

Now you can see that any computation of $\mathrm{depth}\ (\mathrm{full}\ n)$ will first construct the full tree of order $n$ using $\mathrm{full}$ and then deconstruct that tree using $\mathrm{depth}$. Deforestation relies on the observation that such a pattern (construction followed by deconstruction) can often be short-circuited: we can replace any calls to $\mathrm{depth}\ (\mathrm{full}\ n)$ by a single call to $\mathrm{full\_depth}$:

full_depth : Int -> Int
full_depth n | n == 0 = 0
full_depth n = 1 + max (full_depth (n-1)) (full_depth (n-1))

This avoids memory allocation of the full tree, and the need to perform pattern matching, which greatly improves performance. In addition, if you add the optimization

max t t --> t

Then you have turned an exponential time procedure into a linear time one... It would be cool if there was an additional optimization that recognized that $\mathrm{full\_depth}$ was the identity on integers, but I am not sure that any such optimization is used in practice.

The only mainstream compiler that performs automatic deforestation is GHC, and if I recall correctly, this is performed only when composing built-in functions (for technical reasons).


Graph Has Two / Three Different Minimal Spanning Trees? I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal spanning trees. The naive solution that I've though about is running Kruskal's algorithm once and finding the total weight of the minimal spanning tree. Later , removing an edge from the graph and running Kruskal's algorithm again and checking if the weight of the new tree is the weight of the original minimal spanning tree , and so for each edge in the graph. The runtime is O(|V||E|log|V|) which is not good at all, and I think there's a better way to do it.

Any suggestion would be helpful, thanks in advance

Kapoor & Ramesh (proper SIAM J. Comput. version, free(?) personal website version) give an algorithm for enumerating all minimum spanning trees in both weighted and unweighted graphs.

My understanding of the basic idea is that you start with one MST, then swap edges that lie along cycles in the graph (so as long as the weights are okay, you're replacing one edge with another that you know will reconnect the tree).

For the weighted case they give a running time to list all minimum spanning trees of $O(N\cdot|V|)$ where $N$ is the number of such spanning trees. It enumerates them in order of increasing weight, and my current (cursory) understanding suggests that it's perfectly feasible to terminate the algorithm after it has generated a given number of trees (as it just starts with the MST and produces them sequentially).


Given the Equivalence relation R = { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes 1 and 2? Given the Equivalence relation R =  { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes of 1 and 2?

I can't really see the equivalence classes of infinite sets. Only by having a drawing of all elements can I distinguish the answers, wich is not the case in the above mentioned example.

What would be the best way to tackle such problems?

Thanks!

There is no general way to answer such a question other than to repeat the definition. So one might answer for example for $1$:

  The equivalence class that $1$ belongs to is the set of all integers $n$ such that $1 + n \equiv 0 \mod 2$.

You might simplify this by noting that $1 + n \equiv 0$ implies $n \equiv 2-1$ or $n \equiv 1$ modulo $2$, giving:

  The equivalence class that $1$ belongs to is the set of all integers $n$ such that $n \equiv 1 \mod 2$.

Now the answer that the asker is looking for will probably be "the odd integers". If they disagree that the above answer is correct I would argue that the question is too vague however, as in my view the above is perfectly correct.


What is the tightest asymptotic bound for this recurrence? $$T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + T\left(\frac{n}{8}\right) + n$$

How do you solve this recurrence?

It will be $\Theta(n)$, to save myself from rewriting an entire answer, I will refer you to this question and you can apply the answer to your question.


Is concatenation of regular language with any other language regular? I came across following problem:

  True or false?
  If $L$ is a regular and $M$ is not a regular language then $L.M$ is necessarily not regular.

The answer given was:

  Consider $L$ to be $\emptyset$ and $M$ be $\{a^nb^n | n\leq 0\}$
  $L.M=\emptyset$, which is regular. Hence the statement is false.

I guess the solution incorrectly tries to generalize the case of those two specific languages to all other languages. For example, if $M$ is DCFL, then I believe $L.M$ wont be regular. Am I correct with this?

As you show, if $L = \emptyset$ then $LM$ is regular for any language $M$. Conversely, for languages over $\{0,1\}$ (or any non-unary alphabet), there is a language $M$ such that if $L \neq \emptyset$ then $LM$ is not regular:
$$
M = \{10^p : p \text{ prime}\}.
$$
Indeed, suppose that $w \in L$. Then
$$ w^{-1}(LM \cap w10^*) = M. $$
Since all of the operations preserve regularity, we conclude that $LM$ is not regular.

Over a unary alphabet, the picture is a bit different. Let
$$ M = \{ 0^{n!} : n \geq 0 \}. $$
If $L \neq \emptyset$ is finite then $LM$ is not eventually periodic, and so not regular. If $L$ is infinite and not regular, then $L\{\epsilon\}$ is not regular. If $L$ is infinite and regular, then it is eventually periodic. For every language $M$, $LM$ is also eventually periodic (with the same period), and so regular.


Algorithm for clustering points in $\mathbb{R}^2$ based on pairwise distance (percolation graphs) I haven't been able to find literature on the efficient solving of the following problem.

Given $n$ random points $x_i \in (0, 1)^2$ the unit square, obtain the flat clusters of points, such that two points are in the same cluster if their pairwise distance $d(x_i, x_j) < r$, where $r < 1$ is a fixed parameter of the problem.

The naive solution checks each pairwise distance, therefore completing in $\mathcal{O}(n^2)$ time. Is there a faster way, assuming $n$ large and $r \ll 1$?

The following algorithm does unfortunately does not allow you to get the $n^2$ factor out (see comment below).

Superimpose an $r/\sqrt 2$-by-$r/\sqrt 2$ grid on the unit square: notice that every point within the same grid cell is automatically within the same cluster.  Also notice that there can be at most $n$ grid cells containing one or more points; these are the only grid cells we need to consider from this point on.

Map each point to its grid cell.
For each grid cell, throw all contained points into the same cluster.
For each pair of neighbouring grid cells $P$, $Q$ (each grid cell, apart from those at edges and corners, has 8 such neighbours), determine the closest pair of points $p, q$ having $p \in P$ and $q \in Q$ using this $O(n\log n)$ algorithm.  If $d(p, q) < r$ then combine $C(P)$ and $C(Q)$, otherwise not.

You can use a union/find disjoint set data structure to maintain the clusters in close-to-linear time, just as per the Kruskal algorithm.


Not sure how to interpret the question: how to find egg-breaking height I have the below homework question as an assignment of my Computer Science Foundation class.

  Throwing eggs from a building. Suppose that you have an N story building, and plenty of eggs. Suppose also that an egg is broken if it's thrown off floor F or higher, and intact otherwise. First devise a strategy to determine the value of F such that the number of broken eggs is ~lg N when using ~lg N throws, then find a way to reduce the cost of ~2lg F when N is much larger than F.

I'm not entirely sure what the question is asking for. I believe, and what I attempted, is to provide an algorithm as a solution that has a runtime of log N.

From the description of the problem, I attempted to write a binary tree implementation. I'm not sure if this is correct. I'm not asking for an answer, but perhaps some guidance on what the problem is looking for.

In this task, the resources that you care about are not running time, but rather the number of throws and the number of eggs broken (in the worst case). Here is an example. Suppose that $N = 2$. An optimal algorithm, which throws at most two eggs and breaks at most one egg, goes as follows:

Throw an egg from floor 1. If it breaks, the answer is $F=1$. Otherwise, continue.
Throw an egg from floor 2. If it breaks, the answer is $F=2$. Otherwise, the answer is $F=3$.

(If $F=3$ is not a possibility, then we need only one throw.)

In this way, we can determine $F$ using at most $\sim N$ throws and one broken egg. There is a way to improve the number of throws to only $\sim \log N$, at the cost of potentially breaking up to $\sim \log N$ eggs.


Regular expression for $\{x : \#_{01}(x) \mod 3 = 0\}$ Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$.
Give a regular expression that denotes $L_1$, and justify its correctness

Attempt
Believe this is asking for number of $01$'s in $x$ but $|x|$ must be an even number. Like $x = 0101$, $|x| = |0101| = 4 \mod 3 = 1$ wouldn't work. However $x = 010101, |x| = 6$ would work?
How would I make a regex for this?
$R_1 = (01)^*$. How would I do the mod condition?

Note that any amount of ones at the start or zeroes at the end has no influence on the number of $01$ pairs. Then in the middle you want any multiple of three of $01$ pairs, giving:

$$1^*(0^+1^+0^+1^+0^+1^+)^*0^*$$


What is the optimal solution to prove the reachbility of a node from the root? I have a finite automaton with these properties:

Contains cycles
It's a directed graph
All the states/nodes are initialy reachable from the initial state
It has final states but I guess it isn't relevant for my issue
It's a random generated automaton, and the generation isn't meant to satisfy properties like strongly connected components or connected components

Let's suppose I have to delete an edge.

I need to know if there's a way to prove that the reached state by this edge is still reachable from the initial state without using a classical search (DFS or BFS); obviously, if there is any.

This seems to be a difficult problem. For undirected graphs, this is known as "dynamic connectivity". You can see slides describing an $O(\log^2 n)$ algorithm, or the paper itself. For directed graphs, there is an algorithm no better than DFS described in this paper (the algorithm is better than DFS if you are making several connectivity queries each time). A paper by Pătraşcu gives evidence that polylogarithmic update time isn't possible for directed graphs.


Equivalent definition of minimal spanning tree Prove that $T$ is MST $\Leftrightarrow$  for any edge $uv \notin T$, $uv$ has the maximal weight on the cycle created by adding $uv$ to $T$.

It's my attempt to prove $\Rightarrow$:
Consider the cycle $path(v, u) \in T \cup E(v, u)$. If $(v, u)$ is not maximal, replace the maximal edge on the path by $(v, u)$. T is still connected, and we got spanning tree which weight is less than $w(T)$.

But I am stuck with the direction of "$\Leftarrow$".

Note: The original answer has a flaw in "without loss of generality". The following one is based on Section 8.2.3 of the book "Computer Algorithms" (3rd edition) by Sara Baase and Allen Van Gelder.

The right part of the theorem is called the MST property.

  MST Property: Let $T$ be any spanning tree. For any edge $e \notin T$, $e$ has the maximal weight on the cycle created by adding it to $T$.

In terms of the MST property, the theorem to prove can be restated as:

  A spanning tree $T$ is an MST $\iff$ $T$ has the MST property.

We first prove the following lemma:

  Lemma: If $T$ and $T'$ are spanning trees that have the MST property, then $w(T) = w(T')$.

Proof: Let $\Delta E = (E(T) \setminus E(T')) \cup (E(T') \setminus E(T))$. That is, $\Delta E$ is the set of edges that are in one of $T$ or $T'$ but not in both. $\Delta E \neq \emptyset$. Let $|\Delta E| = k$.

If $k = 0$, we are done.

Let $k > 0$ and $e$ be a minimum edge in $\Delta E$. Assume that $e \in T \setminus T'$ (the case of $e \in T' \setminus T$ is symmetrical).

$T' + e$ create a cycle $C_{T'}$. There must be an edge $e'$ on the cycle $C_{T}$ that $e' \neq e$ and $e' \in T' \setminus T$ (otherwise $T$ contains the cycle $C_{T'}$).

Since $T'$ has the MST property, $e$ has the maximum weight on the cycle $C_{T'}$. Thus, $w(e') \le w(e)$.
On the other hand, $e$ by definition is a minimum edge in $\Delta E$. Thus, $w(e) \le w(e')$.

Therefore, $w(e) = w(e')$.

Add $e$ to $T'$, creating a cycle, then remove $e'$, leaving a spanning tree $T''$. Since $w(T'') = w(T')$, $T''$ is an MST. However, $T$ and $T''$ differ by $k-1$ edges.

Repeating the procedure above, we will end with an MST, say $T^{k+1}$, such that $T$ and $T^{k+1}$ differ by $0$ edges.

Therefore, we have $w(T) = w(T^{k+1}) = \cdots = w(T'') = w(T')$.

Given the lemma above, we proceed to prove the "$\Leftarrow$" direction as follows:

Assume $T$ has the MST property. Let $T_m$ be any MST. By the "$\Rightarrow$" direction, $T_m$ has the MST property. By the lemma above, $w(T) = w(T_m)$. Thus, $T$ is an MST.


Determining if we can balance these graph weights Let $G$ be a complete directed graph with $n$ vertices. Each vertex $v$ has a weight $w(v)>0$, such that the sum of all vertex weights is $n$. We have that the edge $e$ from $u$ to $v$ has a weight $0 \leq w(e) \leq w(u)$.

We say that these weights can be balanced, if there exists a directed spanning tree, $T$, and function on the edges of $T$, $f$, where $0 \leq f(e)\leq w(e)$, such that for every vertex $v$, we have that $$w(v) + \sum_{e \in I_v} f(e) - \sum_{e \in O_v} f(e)=1$$ where $I_v$ is the set of all edges in $T$ going into $v$, and $O_v$ is the set of edges in $T$ going out from $v$.

Is determining whether the weights can be balanced a known problem? It sounds like a network flow problem, but I'm not too familiar. What's an algorithm which could solve this?

This solves the problem if the function $f$ is not constrained to the edges of a spanning tree.

You can think of your problem as a flow problem where each vertex $u\in V$ "generates" $w(u)$ units of flow and "sinks" 1 unit of flow.

To reduce this problem to a standard flow formulation you can create a new directed graph $G' = (V', E')$ in which each edge $e \in E'$ has a capacity $c(e)$:

$V' = V \cup \{s,t\}$,  where $s$ is a new "source" vertex and $t$ is a new "sink" vertex.
For each $v \in V$, add to $E'$ the edge $(s,v)$ with capacity $w(u)$.
For each edge $e \in E$, add $e$ to $E'$ with capacity $c(e) = w(e)$.
For each $v \in V$ add to $E'$ the edge $(v,t)$ with capacity $1$.

Compute the value $f^*$ maximum flow from $s$ to $t$ in $G'$. If $f^* = |V|$ then your all units of flow can be generated and sunk (one unit from each vertex $u \in V$), therefore your problem problem admits a solution.
If $f^* < |V|$ your problem admits no solution (to see this you can show that you can convert any feasible solution to your original problem to a flow of $|V|$ in $G'$).


Find an undecidable language that is mapping-reducible to its complement As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All_{TM}, EQ_{TM}, T$ (that is the set of all deciders) satisfy this property. But I tried reducing these to their complements directly, and via some sort of intermediate language, but to no avail. Can anyone help?

Try the following construction. Given a language $L$, use
$$ \{0x : x \notin L\} \cup \{1x : x \in L\}. $$


Asymptotic relation between n! and (n+1)! I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not sure how to write this formally.

I am afraid that you could have been more careful.

  I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$.

By L'Hospital's rule we have $$\lim_{n \to \infty} \frac{(n+1)!}{n!}=\lim_{n \to \infty} (n+1)=\infty\,,
$$ which means $(n+1)! = \omega(n!)$, or what is equivalent, $n! = o(n+1)!$. Note that both $(n+1)! = \Omega(n!)$ and, what is equivalent, $n! = O(n+1)!$ are correct, which are, however, less precise.


Regular language with pumping lemma I have that language $S=\{a^n b^m c^m\mid n,m \geq 0\}$.
How can I prove with the pumping lemma that it isn't regular? Can I use the concatenation closure and say that it's the language $L_1 = \{a^n\mid n\geq0\}$ and $L_2 =\{b^m c^m\mid m \geq0\}$ prove that $L_2$ isnt regular so $L_1 L_2 = S$ is not regular too?

Your concatenation idea doesn't work. Although the concatenation of two regular languages is guaranteed to be regular, the concatenation of a regular language and a non-regular language is not guaranteed to be non-regular. For example, take $L_1=\Sigma^*$, $L_2=\{a^nb^n\mid n\geq 0\}$. $L_2$ is not regular but $L_1L_2=\Sigma^*$ is regular.

To prove that $S$ is non-regular using the pumping lemma, pump a string that contains more $b$s than $c$s.


Gray Code Generation I am trying to generate a $n$-bit gray code where I can specify two strings $s$ and $t$ that must be consecutive in that gray code. I know that there are ways to generate specific codes (such has the Binary Reflected Gray Code and the Recursive Partition Gray Code), but I need to be able to construct one given any two strings as described above. Is there a way to do this? Or a result that guarantees that this is possible? I am almost certain it is, but haven't been able to find anything.

Yes.  It's always possible, if $s,t$ are at hamming distance one from each other.  Let $s,t$ be your two strings at distance one from each other.  Then there exists a Gray code sequence where they are adjacent in the Gray code sequence, say $s$ appears right before $t$.  Now you immediately obtain a valid solution.  Find where $t$ appears in the Gray code sequence, and start going through strings in the Gray code sequence until you get back to $s$.  This will have the property you want, as a Gray code sequence is a cyclic sequence where every adjacent pair of strings has hamming distance one.

How do you find that Gray code sequence?  There are many possible methods, but here's one easy one.  Note that if you have a mapping $f$ on strings that permutes the order of the bits, and you apply $f$ to each element of a Gray code sequence, you obtain another Gray code sequence.  The same is true for a mapping $g(x)=x\oplus c$ that xors the input with a constant string $c$.  These two facts are enough.  Start with any Gray code sequence of your choice; let its first two strings be $a,b$.  Let $s,t$ be your two strings that have Hamming distance one.  Now you can choose $f,g$ so that $g(f(a))=s$ and $g(f(b))=t$ (namely, choose $f$ to move the bit position where $s,t$ differ to the bit position where $a,b$ differ; and then choose $g(x)=f(a) \oplus s$).  This choice of $f,g$ induces a new Gray code sequence: you start with your original Gray code sequence, and apply $f$ to each element of it, then apply $g$ to the result of it.  The result is a new Gray code sequence whose first two elements are $s,t$.  Thus, if you can iterate through the original Gray code sequence, you now have an easy way to iterate through the new Gray code sequence: you just start iterating at its 3rd element, skipping its first two elements (which will be $s,t$).

The requirement that $s,t$ have Hamming distance one is critical, as otherwise there is a trivial counterexample.  Consider 2-bit strings.  Suppose the two strings you already have are 00 and 11.  Then you want to visit the two strings 01 and 10.  However, it doesn't matter what order you visit them in: you won't obtain a solution of the form you want.  In particular, there are only two possible sequences (01,10 or 10,01), and neither one has the hamming-distance-one property you wanted.


Is finding a single digit of a computation is as hard as finding the computation? Let $f: \mathbb{N} \rightarrow \mathbb{N}$ a computable function such that computing $f(n)$ takes $\Omega(2^{2^{2^{|n|}}})$ time in worst case terms and such that the languages:

$$\begin{align*} L_1 &= \{ n \mid f(|n|) = n \} \\
L_2 &= \{ (n,k) \mid \text{the first digit of $n$ is the $k$'th digit of $f(|n|)$} \}\end{align*}$$

Are infinite.

Prove or disprove that $L_1 \leq_{P} L_2$ i.e there is a polynomial time reduction from $L_1$ to $L_2$.

Heuristically I am thinking that for any function it is impossible to compute a digit of the computation without generally computing the function so I am thinking it should be correct, though not sure how to prove it formally.

For some functions $f$ you might be correct. For example, we can arrange that $f(|n|) \neq n$ for all $n$ (by controlling the length of $f(x)$) while keeping $f$ arbitrarily difficult, and so $L_1$ reduces to $L_2$ trivially.

Here is a function $f$ satisfying your constraint, for which $L_1$ does not polynomially reduce to $L_2$. The construction uses diagonalization. (There is some ambiguity in your notation, but the proof can be adapted however you resolve the ambiguities.)

Let $L$ be some computable language which requires time $2^{2^{2^n}}$ (such languages exist due to the time hierarchy theorem). We define the function $f$ as follows: $f(\epsilon) = f(0) = 0$, and $f(0x)$ is the indicator of $x \in L$. We define the rest of the function $f$ by giving an algorithm which eventually defines all remaining values.

Let $\phi_i$ be an enumeration of all functions computable in polynomial time. We can construct such an enumeration using timed Turing machines.  We go over the functions $\phi_i$ in order. When it's time to process $\phi_i$, let $n \geq 1$ be the smallest value on which $f$ is undefined. Let $m = \phi_i(0^n,2)$. We consider several different cases:

Case 1: $f(|m|)$ is already defined. If the second digit of $f(|m|)$ is $0$, define $f(n) = 1^n$, otherwise define $f(n) = 0^n$.
Case 2: $f(|m|)$ is not defined, and $|m| \neq n$. Define $f(|m|)$ arbitrarily, and proceed as in case 1.
Case 3: $|m| = n$. Set $f(n) = 10$.

In all cases, we ensure that $f(n) \neq 0^n$ iff the first digit of $0^n$ equals the second digit of $f(|m|)$, showing that $\phi_i$ is not a polytime reduction from $L_1$ to $L_2$.


pruning branch and bound I am working on a branch and bound problem and I was wondering if it is correct to prune the node with z = 21.667 and if so, how do we know that we will not get a better solution if we branch on this node?

In branch and bound, you prune a branch if you have an upper bound on the best solution that this branch can provide, and this upper bound is smaller than your current best solution. In your case, you have no current best solution (since you haven't considered any integer solutions), and in particular, you cannot prune any branch.


Finding prime factors of non-random key generator I have been working on a challenge i found on the internet. It is as follows:

  You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the random number generator it uses frequently produces the same primes when it is generating keys.

  Exploit this knowledge to factor the (hexadecimal) keys below, and enter your answer as the last six digits of the largest factor you find (in decimal).

  Key 1: 1c7bb1ae67670f7e6769b515c174414278e16c27e95b43a789099a1c7d55c717b2f0a0442a7d49503ee09552588ed9bb6eda4af738a02fb31576d78ff72b2499b347e49fef1028182f158182a0ba504902996ea161311fe62b86e6ccb02a9307d932f7fa94cde410619927677f94c571ea39c7f4105fae00415dd7d

  Key 2:
   2710e45014ed7d2550aac9887cc18b6858b978c2409e86f80bad4b59ebcbd90ed18790fc56f53ffabc0e4a021da2e906072404a8b3c5555f64f279a21ebb60655e4d61f4a18be9ad389d8ff05b994bb4c194d8803537ac6cd9f708e0dd12d1857554e41c9cbef98f61c5751b796e5b37d338f5d9b3ec3202b37a32f

These seem to be common RSA 1024-bit keys.

My approach to the problem was to implement Pollard's rho algorithm to find factors, then once a factor is found, try dividing the decimal form of the keys by that factor until it is not divisible anymore. Iterate.

Now, i used Pollard's rho and tried to divide until the key is not divided anymore because of the information the problem gave: the keys are not completely random.

But here comes the question: assuming the algorithm generates two primes and multiplies them to get a co-prime, which is the key, the low randomness doesn't help much, does it? I mean, even if both keys share a common factor, finding it the first time would take the regular-impractical-exponential time.

That seems to be the case, as my Python algorithm is running for about 5 hours now and has not found any factor to the second key, which i decided to start with.

As it is a challenge, i assume there is a practical way of finding the answer.
So what im i doing wrong? Is just the algorithm choice wrong, as Pollard's rho is intended mainly for integer with small factors? Is my assumption that i can only use the lack of randomness after i find the first of the four factor, to then try to break the other key with the same factor, wrong?

I would like if someone could just point me in right direction, instead of just giving the answer. Thank you.

So you have two numbers that:

both have two prime factors, and
you strongly suspect that they share a factor.

So one is $n_{1}=pq_{1}$ the other $n_{2}=pq_{2}$. What is their GCD?

   What happens when you apply Euclid' algorithm?


Persistent random-access queue I need a queue $[x_0, ..., x_n]$ that supports the following operations:

$\operatorname{enqueue}([x_0, ..., x_n], x) = [x_0, ..., x_n, x]$
$\operatorname{dequeue}([x_0, ..., x_n]) = [x_1, ..., x_n]$
$\operatorname{lookup}([x_0, ..., x_n], i) = x_i$
$\operatorname{update}([x_0, ..., x_n], i, y) = [x_0, ..., x_{i - 1}, y, x_{i + 1},
   ... x_n]$
$\operatorname{insert}([x_0, ..., x_n], i, y) = [x_0, ..., x_i, y, x_{i + 1}, ...,
   x_n]$
$\operatorname{delete}([x_0, ..., x_n], i) = [x_0, ..., x_{i - 1}, x_{i + 1}, ...
   x_n]$
$\operatorname{length}([x_0, ..., x_n]) = n + 1$

All operations should be in $O(\log n)$. The data structure should be atomic and persistent, i.e. it is written to a random-access data storage device, such a hard disk or flash memory. Therefore the data structure should minimize the number of seeks. I thought about using Counted B-Trees without keys and with a rollback journal. I also looked at several purely real-time functional data structures that use multiple lists (lists can be efficiently implemented with a file system with a truncate operation) but they seemed to be too complicated or not randomly accessible.

Assume that the filesystem has the following operations:

write(file, offset, x)
read(file, offset, length)
append(file, x)
truncate(file, length)

Is there any other data structure that I is more efficient or easier to implement while being as efficient?

Yes there is a data structure which name is  Treap   You can also do other things too (ex. range sum, range min-max, etc.) using this or you can also use BBST (Balanced binary search tree like  AVL ).

Okay i will explain some terms i am assuming you have some Knowledge about Trees and BST(Binary search Tree)
Q. What Treap is?
A. Treap = Tree + Heap (in easy way)

Q. Use of Treap?
A. its randomized balanced tree basically its contain 2 values first one is data and second is rank (data, rank) and it has two property using data we keep BST(Binary search Tree) property it mean smaller than data will go on left side and bigger will be on right side and rank keep heap property its your choice that you want min heap aur max heap property. trick here is that rank is given uniformly random. So when we heapify using rank height of tree will not exceed O(LogN). so in easy implementation we can get a self balanced binary search tree.

Q. How to implement above requirements?
A. Insert and Delete methods are easy and equal to BST's methods

struct Node *insert(struct Node *root, int pos, int data) {
  if(root == dummy) {
    ptr ->left = ptr ->rig = dummy;
    ptr ->size = 1;
    ptr ->pri = rand();
    ptr ->data = data;
    return ptr++;
  } else if(root ->left ->size >= pos) {
    root ->left = insert(root ->left, pos, data);
    if(root ->left ->pri > root ->pri) root = rot(root, root ->left);
  } else {
    root ->rig = insert(root ->rig, pos - root ->left ->size - 1, data);
    if(root ->rig ->pri > root ->pri) root = rot(root, root ->rig);
  }
  update(root);
  return root;
}

here you can see 2 methods which are unknown to you actually one it rot which is rotation when our tree violate heap property and update where you can update your tree's attribute here we keeping size so you can updated this information here

Delete method is homework for you it will be same as insert in above code pos define that you want to insert an element in between pos-1 pos.

okay now lets come on your requirements :

enqueue -> call insert and pos will be root ->size
denqueue -> call delete
lookup -> search method same as binary search tree's search method
update , insert -> call insert
length -> root ->size


Tree : Forest :: Path :? A forest is a collection of trees.

Is there a similar notion for paths? e.g., a _______ is a collection of paths.

Wikipedia says that a graph all of whose non-trivial components are paths is a linear forest. Alternatively, you could call it just a disjoint union of paths.


Having a formal ISA specification - What does correctness mean? Does this always mean that a program can be correct in regard to that spec or is there any correctness of the spec itself ?

An ISA spec says how a processor should behave. A processor either conforms to such a spec (behaves exactly like the spec says it should), or it doesn’t (behaves differently in some situations).

ISA has nothing to do with correctness of programs. If a processor conforms to its ISA spec then all programs will behave as they should behave according to the spec, both correct and incorrect programs. If a processor does not conform to the ISA spec then programs can behave different from how they should behave.

A spec cannot be wrong, by definition. It can be nonsensical (like if the spec says that an “add” instruction should subtract, but it’s never wrong.

Reasons for having an ISA spec:

Instructing the team that designs the processor.
Instructing the team that writes test code to test the processor for conformance.
Instructing the team that writes a simulator for the processor which can be used before processors are available.
Instructing teams that write compilers for this processor.
Instructing support teams who handle customer complains about the processor behaviour, so they can check that the processor conforms to the spec.


Why can't we compile 8086 Assembily for all OSs from any OS? If Mac OS, Linux, and Windows (mostly) all use Intel's 8086 64 bit instruction set, why can't we compile 8086 64 assembly from any operating system to any other operating system? (e.g. compile a Mac OS executable from assembly in Windows). Surely it would just be a matter of knowing what the machine code is for any given instruction?

Porting to a different operating system is about a lot more than the particular assembly language you use.  Different operating systems have different system calls, different libraries, and different APIs, and converting from one to another is usually not something that can be done in an automated way -- even if both used exactly the same assembly language.  Most programs do need to access the filesystem, the network, display things on the screen, and so forth, and all of those require interaction with the OS and libraries.


How is verifying whether an assignment satisfies a boolean formula possible in polynomial time? How can I prove that I can verify whether a boolean assignment of variables $a$ satisfies some boolean formmula $\phi$ in polynomial time?

I know that we can just plug the boolean assignment into the formula, but this seems to be a very high-level description, and I am not sure that it is a reliable one since we must simplify the formula.

There is no need to simplify the formula, you just evaluate it recursively according to the definition of the boolean operators in use.

Let $\varphi$ a boolean formula and $a : X_\varphi \to \{0,1\}$ an assignment of all variables that occur in $\varphi$. Now we define the evaluation function $\operatorname{eval}_a$ on variable-free boolean expressions in the following way:

$\qquad \begin{align}
  \operatorname{eval}_a(\text{true})  &= 1 \\
  \operatorname{eval}_a(\text{false}) &= 0 \\
  \operatorname{eval}_a(x) &= a(x) \\
  \operatorname{eval}_a(\lnot \varphi) &= 1 - \operatorname{eval}_a(\varphi) \\
  \operatorname{eval}_a(\varphi \land \psi) &= \operatorname{eval}_a(\varphi) \cdot \operatorname{eval}_a(\psi) \\
  \operatorname{eval}_a(\varphi \lor \psi) &= \max(\operatorname{eval}_a(\varphi), \operatorname{eval}_a(\psi)) \\
 & \vdots
\end{align}$

Clearly, $\operatorname{eval}_a(\varphi) = 1$ if and only if $a(\varphi) \mathop{|\!\!\!==\!\!\!|} \text{true}$ (here, $a$ is continued on $\varphi$ in a syntactical manner: it replaces all variable occurrences $x$ in $\varphi$ with $a(x)$). If in doubt, perform a structural induction along the inductive definition of boolean formulae. Furthermore, $\operatorname{eval}_a$ performs about one operation per operator and literal; thus it runs in time $O(|\langle \varphi \rangle|)$.


NP-completeness for integer linear program This is a homework problem, so I don't want the solution. I need a hint which problem to reduce to the following and/or how to start on it. We were thinking of TSP or independent set but couldn't come up with a solution.

We have $i\ldots j$ stores and $i\ldots n$ possible places to build a new warehouse. Costs to build a new warehouse are $c_j$. Between each store and warehouse is a path of cost $d_{i,j}$. Every store needs to be connected to at least one warehouse.

The decision problem is: is there a set of warehouses and paths so that the sum is smaller than a given number $k$.

This is a classic facility location problem. That Wikipedia article suggests that NP-hardness can be proven by reduction from set cover.

Since the asker has now stated to have found a solution by reducing from vertex cover, I will go ahead and reveal the reduction from set cover:

   For each value, create a store; for each set, create a warehouse. Assign the cost of each warehouse to be 1. Assign the cost of the route from a warehouse to a store to be an arbitrarily small value if that warehouse's set contains that store's value, or an arbitrarily large value otherwise. Then the minimum cost solution to the facility problem builds precisely the set of warehouses corresponding to the minimum set cover in the original problem.

 The $k$ value is used to turn the optimization problem (minimize sets/cost) into a decision problem (is there a solution with no more than $k$ sets/cost?). The $k$ from the set cover instance will be the same as the $k$ in the facility problem instance if you are allowed to set the "arbitrarily small" values to exactly 0 - otherwise you might have to fudge the value by some amount, but less than 1 as long as you pick the "arbitrarily small" weights to be small enough. You just need the total of every "arbitrarily small" cost to be less than 1, and every "arbitrarily large" cost to be greater than the sum of the costs of all the warehouses and all the "arbitrarily small" routes.

 Note that, if only integer costs are allowed in the facilities problem, you can still achieve the same result by scaling all the costs by their least common multiple.


Operator name in LL(1) computation I'm working from a definition of the LL(1) property of context-free languages in order to build a LL(1)-computer, i.e., a program capable of determining whether a given context-free language is in LL(1).

The definition requires the disjointness of certain sets; each set is defined as an infinite limit, but practically calculated via fixed-point iteration of an inductive, case-based equation.

Present in these equations is the definition of a new operator to simplify the notation (let $\epsilon$ be the empty sequence):

$$\forall S,T : S \oplus T = \begin{cases}
  S & \epsilon \not\in S \\
  (S \setminus \{\epsilon\}) \cup T & \epsilon \in S
\end{cases}$$

I know this operator in latex as \oplus. In an attempt to write readable-code, I want to give this operator a name (and endow scala Sets with a trait that expresses this name).

Is there a traditional name for this usage of $\oplus$? If so, what is it?

Bonus points: if the name is, e.g., add, is there an acceptable word like addable with the meaning that two objects—mathematical or code—are capable of being added?

A set of values that comes with an "add" operation that is associative is called a semigroup.  If it also comes with an element that plays the role of 0 (so that 0 + x = x and x + 0 = x for all x), it is a monoid.

In your case, you have a monoid, as $\{\epsilon\}$ plays the role of 0 (it is an identity).


Doubt on Performance Comparison of Splay Trees I'm trying to understand splay tree performance compared to a standard balanced tree like AVL/red-black. In practice, I am pretty skeptical of the amortized bounds Tarjan and Sleator proves in their paper. Maybe because I am not that smart to actually understand these proofs, but I am still curious of one certain pathological case.

Suppose that we have a splay tree with $n$ nodes. These nodes are ordered from $1$-$n$ according to their height/level in the tree. You then access them starting from the highest level to the lowest level nodes ($n$ to $1$). In this way, it would guarantee the worst case access sequence of the tree. My intuition says that this case would be significantly slower than an AVL tree. It's probably proven somewhere that even in this case, the asymptotic access time is the same. However, I am also accounting for constant factors for a direct comparison of raw performance. How practical are they in real world application?

There has been various real world applications that use splay tree. One of the most prominent example is the gcc compiler that applies splay tree. There are many other examples. In fact, ACM Kanellakis Theory and Practice Award 1999 was given to Daniel Sleator and Robert Tarjan for their seminal work on the splay tree data structure.

It looks like you have some misconception on the splay tree about its worst performance.

Take the example you have mentioned, where we access a splay tree of $n$ nodes that labelled from $1$ to $n$ according to their level in the tree, starting from $n$ down to $1$. Your intuition indicates "this case would be significantly slower than an AVL tree." Indeed, the height of the tree before and after those search operations is $n-1$. That is, the tree is the most unbalanced tree before and after that search operations.

However, contrary to your intuition, it turns out that case is a showcase of the stellar performance of a splay tree. Although an $O(n)$-time operation is needed to access the first few nodes, the average cost for all search operations is smaller than a constant that is not dependent on $n$ (assuming the usual RAM arithmetic computation model)! In fact, we have the sequential access theorem for splay tree, which says that if you look up all $n$ elements in a splay tree in ascending or descending order, the amortized cost of each lookup is $O(1)$. You cannot achieve such amazing performance with any kind of search tree that keeps intact during a search, including an AVL tree. To experience that phenomenon, you can go to splay tree visualization. Enter $32$. Hit "insert". Enter $31$. Hit "insert". And so on until you have inserted $1$. Then find $32, 31, \cdots, 1$. Observe what is happening.

Once you have that experience, it is not hard to understand that extraordinary phenomenon. After initial about $\log_2(n)$ search operations, the tree becomes almost completely balanced, that is, its height is about $\log_2(n)$. Since that point of time on, accessing each next node will take at most $\log_2(n)$ time. Furthermore, whenever a node that is somewhat far from the root is accessed, the nodes along its path to the root are brought up significantly closer to the root. In the end, the vast majority of the nodes will be found within some constant time.


Compute single-source shortest paths in O(n+m) time? I found the following problem in my textbook and I'm having trouble with coming up with a solution. I'm thinking maybe there's a way to improve Dijkstra's algorithm by using a data structure other than a priority queue, since that's what causes the log(n) time complexity, but I'm a bit lost. Here's the question:

Suppose you are given a connected weighted undirected graph, G, with n vertices and m edges, such that the weight of each edge in G is an integer in the interval [1, c], for a fixed constant c > 0. Show how to solve the single-source shortest-paths problem, for any given vertex v, in G, in time O(n + m).
Hint: Think about how to exploit the fact that the distance from v to any other vertex in G can be at most O(cn) = O(n).
The "single-source shortest-paths" problem, is a problem in which we are given one vertex along with several nodes in a graph, and we are required to find the shortest path to any other node, given the edge length between each node.

I really appreciate any help in advance!

There are many ways to solve this problem in linear time. I'll write the one I found easiest to understand.

The main idea is to transform the weighted graph into an unweighted one. If the number of nodes and edges of the transformed graph remains linear to $n$ and $m$, then we can run BFS to solve it in $O(n+m)$.

The transformation is as follows: for each edge $(u,v)$ of weight $w$, create $w-1$ nodes to connect $u,v$. For example an edge $(a,b)$ of length $3$, we create two dummy nodes and transform it into

$a-d_1-d_2-b$

It is easy to check that this transformation preserves the shortest path between any pairs of nodes. The number of nodes is now $O(n+cm)=O(n+m)$ and the number of edges is $O(m+cm)=O(m)$. Since BFS is linear to the number of nodes and edges, we have a runtime of $O(n+m+m)=O(n+m)$.


Time complexity of binary search Proposition: The binary search algorithm runs in $O(\log n)$ time for a sorted
sequence with $n$ elements.
When justifying this claim, first we say that with each recursive call the number of candidate entries still to be searched is given by the value
$$ high - low + 1 $$
The middle index, $mid$, is given by
$$ mid = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor $$
We say that the number of remaining candidates is reduced by at least one half with each recursive call. Hence the number of remaining candidates, $n$, when we shift our $high$ index to the $(mid - 1)$ index is given by:
$$ n = (mid - 1) - low + 1 $$
$$ n = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor - 1 - low + 1 $$
$$ n = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor - low  $$
$$ n \le \Biggl\lfloor\frac{high  -low + 1}2\Biggr\rfloor $$
This is the part I don't understand how did we get from the equality equation to the inequality equation?
Again, when we are computing the maximum number of recursive calls performed, $r$, we say that $r$ is the smallest integer such that
$$ \frac{n}{2^r} < 1 $$
So:
$$ r > \log n $$
$$ r = \lfloor \log n \rfloor + 1 $$
Similarly, how did we get from the inequality equation to the equality equation?
Any help will be appreciated to help me understand this proof.

Let me start with the first question. Since $\lfloor x \rfloor \leq x$,
$$
\left\lfloor \frac{\mathit{high}+\mathit{low}}{2} \right\rfloor - \mathit{low} \leq
\frac{\mathit{high}+\mathit{low}}{2} - \mathit{low} \leq
\frac{\mathit{high}-\mathit{low}}{2}.
$$
To complete the proof, we use the inequality $\frac{x}{2} \leq \lfloor \frac{x+1}{2} \rfloor$, which holds for integer $x$. To see this, notice that for even $x = 2y$, the inequality reads $y \leq y$, and for odd $x = 2y+1$, it reads $y+1/2 \leq y+1$.
Now for the second question. We want to know what is the smallest integer $r$ such that $r > \log n$. Since $\lfloor x \rfloor > x-1$, we see that $\lfloor \log n \rfloor + 1 > (\log n - 1) + 1 = \log n$. On the other hand, since $\lfloor x \rfloor \leq x$, we see that $\lfloor \log n \rfloor \leq \log n$, and in particular, it is not the case that $\lfloor \log n \rfloor > \log n$. Therefore $\lfloor \log n \rfloor + 1$ is smallest integer $r$ such that $r > \log n$.


Implication of Berman and Hartmanis conjecture I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture :

  All $NP$-Complete languages are $p$-isomorphic.

Then the book says that if the conjecture is True then $P \ne NP$. I am unable to make sense of the proof the book gives, which is:

  If $P=NP$ then all languages in $P$ are $NP$-Complete, but there are finite languages in $P$ and these cannot be $p$-isomorphic to infinite languages.

Two languages $X$ and $Y$ are $p$-isomorphic if there's a polynomial-time computable bijection $f\colon X\to Y$ such that $w\in X\iff f(w)\in Y$.

Now, suppose that P$\,=\,$NP.  Assuming we're defining NP-completeness in terms of polynomial-time many-one reductions, every language in NP, except for $\emptyset$ and $\Sigma^*$ is NP-complete.  To see this, let $Y\in\mathbf{NP}\setminus\{\emptyset, \Sigma^*\}$ and pick two strings $w_{\mathrm{in}}\in Y$ and $w_{\mathrm{out}}\notin Y$. For any language $X\in \mathbf{NP}$, we can reduce $X$ to $Y$ in polynomial time using the function
$$f(w) = \begin{cases}
\,w_{\mathrm{in}} &\text{if }w\in X\\
\,w_{\mathrm{out}} &\text{if }w\notin X\,.
\end{cases}$$
Since $X$ can be decided in polynomial time, we can compute $f$ in polynomial time.  Note that there is a small error in the proof quoted in the question, which claims that all languages in P would be NP-complete if P$\,=\,$NP.  This is incorrect: if we took $Y=\emptyset$ or $Y=\Sigma^*$, the reduction wouldn't work because one of $w_{\mathrm{in}}$ and $w_{\mathrm{out}}$ wouldn't exist.

So, we've established that, if P$\,=\,$NP, then every finite language is NP-complete; we also know that some infinite languages, such as $\mathrm{SAT}$ are NP-complete.  But now suppose that there's a $p$-isomorphism between every pair of NP-complete languages.  That means that, in particular, there's a bijection between every finite language and $\mathrm{SAT}$. But there can't be a bijection between a finite set and an infinite set.


Regular languages and sets proof I just have general questions about sets and determining if they are regular languages.

i) If A is regular, and A is a subset of B, then B must be regular.

ii) If B is regular, and A is a subset of B, then A must be regular.

iii) If A and AB are regular, than B must be regular

iv) If Ai is an infinite family of regular sets, than the union  of all those sets is regular.

For the third one, I know that AB can only be regular if B is regular, because a regular set * a irregular one is not regular.

Lost for the other ones.

Always think of boundary cases. In this case - the languages that contain every string or no string.

Also, let $N$ be some arbitrary non-regular language.

i) The language that contains no strings, which is regular, is a subset of $N$.

ii) $N$ is a subset of the language that contains all strings, which is regular.

iv) For every string $S_i$ in $N$, construct a set $L_i$ that contains only $S_i$. Note that all of these constructed sets are trivially regular. But the union of all of these (infinite number of) constructed sets is $N$, which is not regular.


Equivalence of GFp and Gp in LTL In linear time logic, is $\mathbf{GF}p$ equivalent to $ \mathbf{G}p$ ?

$\mathbf{GF}p$ means that it is always the case that p is true eventually.

Let $\mathbf{G} p$ be defined as: $\forall j \ge0,\  p$ holds in the suffix $q_j, q_{j+1}, q_{j+2},\ldots$

and since:
formula $φ$ holds for state machine $M$ if $φ$ holds for all possible traces of $M$

Isn't $\mathbf{G}$ in $\mathbf{GF}p$ redundant then?

No, not equivalent and not redundant.

Consider $p$ being true if and only if $j$ is even.  $\mathbf{G}p$ is not true (obviously, since $p$ is false in every odd state), but $\mathbf{GF}p$ is always true.


Check if a relation is reflexive, symmetric and transitive I want to better understand how this actually works, as my solutions are
sometimes not 100% correct.
I have the following relation:

Check if the following relation is reflexive, symmetric, and/or
transitive:
$$ R_1 = \{ (x,y) \mid x,y \in \mathbb{R}, x=0 \land y \geq 0 \}. $$

so by that
$$ R_1 = \{ 00, 01, 02,03,04,05,06,07,08,09,010, \dots, 0R_+ \} $$
Basically $R_1$ is 0 and any $R_+$ number.
It is not reflexive, as $(a,a)$ is not in $R_1$.  I only have 00, but
not 11 or 22 and so on.
It is also not symmetric, as I don't have 01 and 10 or 02 or 50 and
05. So $xRy$ and $yRx$ are not true for $R_1$.
As for the transitivity, well, if $xRy$ and $yRz$ then $xRz$.  Well,
this one is hard to understand. I could use 00 as an example: If $y = 0$
and $z \geq 0$ then $xRz$ would work.  So I would say it is transitive.
Can anybody confirm if this would be correct? If not, i would really
appreciate a correct approach then for this task.

"If xRy and yRz": Look at the definition of R. You have x = 0 and y ≥ 0 because xRy. You have y = 0 and z ≥ 0 because of yRz. If you have xRy and yRz then you have x = 0 and z ≥ 0, therefore xRz. So R is transitive.
In total you know that x = 0, y = 0 and z ≥ 0, so you also have yRx, although nobody cares much about that.


Intersection of two incomplete DFAs Let assume that I have the following two automata A1 and A2 :

I have to do the intersection of the two, so I did this :

My question is related to the "∅". If I have two incomplete automata without dead states, and given a specific state, one automaton has a transition for one symbol but the second doesn't have it, what should I do ?
For example I am in the state 13 in the transition table and I read "b", should I rather put ∅ or 4 and make it non final ?

To answer the question, there are two different manners to solve this.

By adding a dead state whenever you have an incomplete automata. By doing so, you will no longer have to worry about what to do if one automata has a transition from a specific state but not the other.
You can still do the intersection of the two without adding dead states.

In this example, if you are focusing on the state 1 and 3 with the symbol 'b' :
- From A1, you have no transition : δ(1,b) = ∅
- From A2, you have a transition : δ(3,b) = 4

Since one has a transition, but not the other, then the resulting automata will have the transition : δ(13,b) = ∅. Therefore, it is indeed acceptable to put ∅.


Algorithm for cycle-detecting comparison I am looking for an algorithm that I can use to compare nested and potentially recursive data structures, for example to implement the Scheme equal? function.  equal? recursively compares two objects for equality and properly handles cycles.  Specifically, the algorithm needs to return true iff the (possibly infinite) unfoldings of the graphs would be equal, e.g.

(letrec ((a (cons 1 (cons 2 a)))
         (b (cons 1 (cons 2 (cons 1 (cons 2 b))))
  (equal? a b))

is true because a and b are both cyclic lists that repeat the sequence (1 2) infinitely.

Destructive modification of traversed nodes is thread-unsafe, requires a spare bit in object headers, and requires a separate traversal to reset the bit.  Using a hash table to store object addresses is not safe in the presence of a moving garbage collector unless the GC is blocked for the duration of the traversal (so the operation cannot be implemented except as a primitive).

There is no pure way to detect cycles, where by pure I mean without caring about representation details such as object addresses. If you only allow examining data by comparing fields at base types, then there is no way to distinguish e.g. a cyclic list from a very long list. If you start examining

(1 2 3 4 5 6 7 8 9 10 11 …
(1 2 3 4 5 6 7 8 9 10 11 …

then maybe one of them is the list (1 2 3 4 5 6 7 8 9 10 11) and the other is (repeat (1 2 3 4 5 6 7 8 9 10 11) where (repeat cycle) builds a cyclic list that repeats its arguments — but you need to examine one more node to find the difference. Since the difference could be arbitrary far, there's no way to prove that two cyclic lists are equal.

The most practical solution is to compare object addresses to detect cycles. I expect that this is how most Scheme implementations do it. This requires some knowledge of how the garbage collector works, and specifically the ability to temporarily prevent it from relocating any object that is within the already-traversed part of the data structure. Locking GC moves might not hurt much, it depends on the GC technology: a mark-and-sweep GC doesn't need to move objects.

By the way, mark-and-sweep GC usually detect cycles by using a spare bit in the object. But that doesn't generalize well to arbitrary processing of arbitrary data structures.

If you're building your own data structure, as opposed to having to cope with arbitrary data structures like equal?, then a good approach is to not store cycles. Purely functional data structures typically don't have cycles in the first place since they can only create cycles with a statically-known structure which is not very useful. As with many problems in computing, this is solved by adding a level of indirection: instead of having the data structure contain a pointer chain that loops back to itself, have it contain references, i.e. the data structure is represented as some kind of map from identifiers from elements and nested data structures are stored using their identifier. When doing this, it's useful to perform hash consing, i.e., when applying a constructor, verify if the result is already referenced in the map and if so use the existing identifier rather than making a new one. This can save memory, and also processing time since traversal algorithms never need to handle the same data structure twice. In particular, with this trick, you can test equality of data structures by simply testing equality of identifiers.


Find optimal quantum at Round Robin Scheduling algorithm In this process list situation

How can I find the quantum time ( time slice ) at 80% of CPU time ?
I found only for 100% of CPU time, so I don't know if it's the same for 80% case

B.T.Q= [mean + median ] / 2
mean=(P1+P2+P3+.....Pn) / n

Never mind, I just found how to take the quantum time. Just find 80% of n processes Eg: You have 9 process, 80% from 9 is 7.2 ~ 7. Order the process ascending by BURST and take the burst from 7 process.


How do I compute the luminance of a pixel? I have a color (say $R=100, G=150, B=130$). How do I compute its intensity?

Do I just sum up all three components? Or are the colors not evenly weighted?

The colors are not evenly interpreted by our eyes.  When I want to make a picture gray scale, I usually go for the following calculation of the luminance of a pixel.

luminance = (r * 0.3) + (g * 0.59) + (b * 0.11)

Read more in the Stackoverflow question Formula to determine brightness of RGB color.