Sorting in a probabilistic order Given a list of real numbers $p_1, \dots, p_n$, I am looking for a most efficient algorithm to sort this list in a "probabilistic ascending order", meaning that $p_i < p_j$ implies that it is likely for $i$ to be placed before $j$, but not certain. In principle, every permutation is a possible output, but the less sorted the permutation is, the less likely it is to occur.

The best solution I could come up with is to modify selection sort. Instead of selecting the minimal element in every step, you select a random element with probability proportional to $\frac{1}{p_i}$. This has quadratic complexity of course, so I was wondering if there are better alternatives.

One of the popular models for biased permutations is the Mallows model, dating to a paper of Mallows from 1957. Lu and Boutilier, quoting Doignon et al., give the following recipe for sampling a permutation according to the Mallows distribution, given a parameter $0 < \phi \leq 1$:

Start with the permutation 1.
Insert 2 into position 1 with probability $\frac{\phi-\phi^2}{1-\phi^2}$, and into position 2 with probability $\frac{1-\phi}{1-\phi^2}$.
Insert 3 into positions 1,2,3 with probabilities
$\frac{\phi^2-\phi^3}{1-\phi^3},\frac{\phi-\phi^2}{1-\phi^3},\frac{1-\phi}{1-\phi^3}$, respectively.
Insert $4,\ldots,n$ in an analogous manner.

When inserting $x$ into position $i$, what you do is shift positions $i,\ldots,x-1$ one step forward, and insert $x$ in the resulting empty spot.

The probability to obtain a permutation $\pi$ is proportional to $\phi$ raised to the number of inversions in $\pi$ (the Kendall $\tau$ distance between $\pi$ and the identity permutation).

Another popular model is the Plackett–Luce model from 1959. There are other models, for example Tallis–Dansie.

The expected running time of quicksort with random pivot is actually $O(n\log n)$.

One can show that you cannot achieve better expected runtime, by any randomized algorithm that correctly sorts any list of $n$ elements. This is shown by Yao's principle, which states that the worst case expected running time of any randomized algorithm, is no better than the expected running time of the best deterministic algorithm for any input distribution.

This gives you the power to, instead of considering coin tossing algorithms, fix some input distribution, and ask what is the best expected running time of any deterministic algorithm relative to that distribution (i.e. it relates randomize complexity to distributional complexity).

Now, since we can fix any distribution, you can look at the uniform distribution over all possible inputs, and ask what is the best expected running time a deterministic algorithm achieves, relative to the uniform distribution.
A lower bound proof in this setting is closer in spirit to the regular lower bound proof for deterministic sorting that you know, you can find it in the following lecture notes.

The idea is similar, you consider a comparison based sorting algorithm as a binary tree, where each node is a query of the form $x<y$, and each leaf in the tree represents a different permutation. The number of comparisons required to sort some input $a_1,...,a_n$ is given by the height of the leaf corresponding to the sorted permutation $a_{i_1},...,a_{i_n}$. Since the number of leaves is $n!$, you know the depth is $\Omega(n\log n)$. The difference in the distributional case is that you need to bound the average leaf height of a binary tree with $n!$ leaves (not the depth). Now, proceed to show that the average leaf height is minimized by a balanced binary tree, in which the average leaf height is $\Omega(\log n!)$. To see why you can focus on balanced trees, show that if the tree is unbalanced somewhere, you can "fix it", and this operation only decreases average leaf height.

I only dealt with algorithms that correctly sort all inputs, but using Yao's principle for Monte-Carlo algoirthms, you can extend this to your case.


Key differences between interactive and time sharing operating systems? Couldn't find much online on how an interactive system is different from a time-sharing system, or the different traits of both.

My understanding of a time-sharing system is many people at terminals being able to use the system at the same time, and the CPU's aim is to maximise response time not CPU time (unlike a multiprogrammed batch system). The switches between jobs are very frequent, and users get immediate responses, when for example submitting interrupts via keyboard inputs. There is very little CPU idle time, duplication of software etc, but it is less reliable, there might be lower security and integrity, and potentially bad data communication. An example would be a chat messaging client or system.

Time sharing is a system of multi-tasking designed to allow multiple users to use a single machine at the same time.
A time sharing operating system is one that supports multi-tasking and multi-user.
In a time-sharing system the user typically interacts with the operating system through a secondary machine called a terminal.

In an interactive operating system there is typically only one user on the system that has full control over the system.

Because of the environment in which time-sharing machines are used (large cooperations and banks) security and separation between users is a prime concern.

Interactive computing originates from the hobby and personal computing revolution. Because there is only a single user security was initially not a concern.

From these starting points the lines have blurred.
First single user systems gained multi-tasking and then multi-user concepts were copied over from time-sharing systems into the interactive OS'es.

Meanwhile the security and performance of time sharing systems have also improved.

Your understanding is quite accurate. The main concern on time sharing systems is that the system appear responsive to interactive users.

I am not aware of any difference between the meaning of two terms in the context of operating systems. 'Interactive' just connotes to a property of an OS.


Language is recursive, hence recursively enumerable I was going through a book of proof and I read:

  If L is recursive, L is r.e.

And the proof goes:

Let L be recursive, hence there is a TM that decides it
Convert an halt state to a normal state
Add to program that when it enters this state it goes to infinite loop

How can this be a proof for it?

Depending on what definitions you use, the proof can be trivial.  We can all agree that a set $S$ is recursive if there is a Turing machine that halts on every input, accepts the members of $S$ and rejects the non-members of $S$. Such a Turing machine is called a decider of the set.

One definition of the recursively enumerable sets is that $S$ is RE if there is a Turing machine that accepts every member of $S$ and does not accept any non-member.  That is, if $x\notin S$, the machine either rejects it or loops forever.  By this definition, it is trivial that every recursive language is RE: the machine that decides the language has the property that it accepts everything in the set and nothing outside it.

The other definition is that a set $S$ is RE if there is a Turing machine that accepts every member of the set and loops forever for every non-member.  This appears to be the definition your book is using.  Now, suppose you have a machine that decides a set $S$.  Modify it so that, instead of rejecting non-members of the set, it loops forever.  This gives a machine that accepts every member of $S$ and loops forever for every non-member.  This is exactly what you need to conclude that $S$ is RE.

The same idea proves that the two definitions of RE are the same.  Any machine that obeys the second definition also obeys the first one (the first says it can either loop or reject for non-members: it happens to loop for all of them but that's a valid choice).  Any machine that obeys the first definition can be converted to obey the second by the same trick: replace rejection with looping.

The class R is a proper subset of the class RE and this is just a trivial consequence of the definition of these classes.
Basically a Language L is in R iff both L and (not)L are in RE.
So if something is in R it must be in RE.In the proof you have presented this idea is illustrated by sort of handicapping the TM by enabling it to satisfy only one of the 'anded' conditions.


Path in directed, weighted, cyclic graph with total distance closest to D? Input: Directed, weighted, cyclic graph G. Two distinct vertices in that graph, A and B, where there exists a path from A to B. A distance d.

Output: A path between A and B with distance closest to d. The path need not be a simple path - it can contain repeated edges and vertices.

Which algorithms exist to solve this problem? I'm looking for an optimal solution, but I'm also interested to see if there are any approximation algorithms as well. Efficiency is not a huge concern - I just want to get an idea of the algorithms available.

Bonus question: are there any algorithms to compute a path from A to B that visits every node at least once, while finding the distance closest to d?

The problem is NP-hard, by reduction from subset sum (given weights $w_1,\dots,w_n$, take a graph with $n$ vertices and two edges from vertex $i$ to vertex $i+1$, one of weight zero and one of weight $w_i$).

One algorithm is to simply enumerate all paths up to a certain length (say, up to length $2d$, if all edge weights are non-negative).  This can be done by enumerating all paths of length $i$; then enumerating all paths of length $i$ by concatenating any path of length $i$ followed by any edge out of the final vertex of that path; and so on, for $i=1,2,3,\dots$  Of course, the algorithm takes exponential time, but it is an algorithm.

I could be wrong but this looks like a classic Dijkstra's algorithm problem. If you aren't familiar with the algorithm you can read more about it at Wikipedia, or you can read about the original variant of the algorithm from this paper written by Dijkstra himself here.


detect closed shapes formed by points I plot several arrays containing xy-coordinates of points (using plot(x,y)) and obtain a plot with some curves. The curves form some very distinctive closed shapes (that is, the points describing the curves lie close to each other).

Now I need to find the (possibly approximate) centers of the closed shapes. Alternatively, it's good to "recognize" the closed shapes and to fill them. I don't know what is easier given the coordinates of points forming the shapes.

A possible example with 3 closed shapes to detect is given below.

Points can be also added along the image's borders, thus, closing all open shapes. Then all "regions" in the figure will be closed, but the question persists.

find all intersections by checking all pairs of segments, belonging to different curves. Of course, filter them before real check for intersection.
Number all curves 1..n. Set some order of segments in them.
For every point create a sequence of intersections SOI, so: if it starts from the border end, SOI[1] is null. If not, SOI[1]= (number of the first curve it is intersecting with, the sign of the left movement on the intersecting curve). Go on, writing down into SOI every intersection - number of curve if there is some, or 0 if it is the intersection with the border.
Obviously, you are looking only for simple bordered areas, that have no curves inside.
Pieces of curves between two adjacent non-null intersection points we'll call segments.
Having SOI for each curve:

for segment of the curve 1, starting from the first point of the segment, make 2 attempts to draw a polygon of segments. It is 2 because you can go to 2 sides along the first intersecting curve.
For the right attempt, make only left turns, for the left attempt, make only the right turns.
If you arrive at point with no segment in the correct direction, the attempt fails. If you return to the curve 1, it success. You have a closed area.
Remember all successful attempts
Repeat this for all segments of curve 1
Repeat this for all other curves, checking all found areas against the already found ones. Two same adjacent segments is enough to consider areas equal.

Edit:
How to find the orientation of the intersection.

When segment p(p1,p2) crosses segment q(q1,q2), we can count the vector multiplication of vectors pXq. We are interested in only sign of its Z coordinate - that is out of our plane. If it is +, q crosses p from left to right. If it is -, the q crosses p from right to left.

The Z coordinate of the vector multiplication is counted here as a determinant of matrix:

0         0          1
p2x-p1x   p2y-p1y    0
q2x-q1x   q2y-q1y    0

(of course, it could be written more simply, but it is a good memorization trick)

Of course, if you'll change all rights for lefts, nothing really changes in the algorithm as a whole.

Here you go:

1) Do not draw the axis

2) Do not draw the plots with * but plot it with - .

3) Also plot $y=-0.02$, $x=-0.02$, $x=0.08$ plots. Plot the upper boundary as well.

4) Now take a screen capture. The bigger the plot, the more accurate the result will be.

5) Normalize the image to $0-1$. (Make it logical as in $logical(I)$)

6) Apply connected component labeling (supposedly in matlab using bwlabel etc.) - If you are not familiar with this part, I could elaborate.

Now you have closed shapes as connected binary regions. You can compute the region properties with : http://www.mathworks.com/help/images/ref/regionprops.html

Center and area are just 2 properties of these regions.

7) If you want to paint those regions on the image you could as well do so, since you have every point in the region.

If you don't have the image processing toolbox, then let me put it this way (exactly the same operation):

Sufficiently discretize your grid (adjust grid resolution so that the accuracy is sufficient for you). Each discrete point (a.k.a pixel) will be a node in your grid. Then for all grid locations other than the actual data points, form a connectivity graph (adjacency graph). This will connect the neighboring nodes (Use 4 or 8 connectivity) Then apply Tarjan's strongly connected components analysis to it: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm .

At this point, you will end up a component label per each node. This is the same as obtaining the connected components from the image. After that, you could retrieve each discretized point on the grid separately to compute the centroid, area or you can visualize these by label coloring.

Hope this helps.
Cheers,


Efficient algorithm for rectangle containment Given a set of $n$ intervals on a line, there is a $O(n \log n)$ algorithm to find intervals which are contained in other intervals (e.g., Manber, "Using induction to design algorithms", 1988).  Is there a $O(n \log n)$ algorithm for axis-aligned rectangles in higher dimensions?

I did some search on the internet, and tried to think about it myself, but could not find a generalization for higher dimensions.  For example, given $n$ axis-aligned rectangles on the plane, the task is to find which rectangles are contained in other rectangles.

Have you considered multi-dimensional indexes? They are usually quite efficient to find overlapping or included rectangles.

I personally wrote a kind of prefix-sharing binary quadtree: Java sources
It has an API for rectangles with a special method for searching rectangles included in another rectangle: PhTreeSolidF.queryInclude().

I'm not sure what the complexity is but it's roughly something in the order of O(n*k*log n) to build the tree and O(k*log n) for each query (k is the number of dimensions). For strongly clustered datasets it may even become something lose to O(1) for each query (I tested this with n=10.000.000 and 2<=k<=15).

there is a natural extension/ generalization of range searching for axis-aligned rectangles and higher dimensional hypercubes.

the problem reduces to checking range inclusion on each axis separately and then finding the intersection of the rectangles or hypercubes that "own" each 1-d range inclusion. it takes k*O(f(n)) where f(n) is the time to check a single dimension and k is the number of dimensions. this is based on the simple idea that for axis aligned rectangles/ hypercubes, a hypercube is in another hypercube iff all its separate sides are also. this does not determine merely overlapping axes-aligned rectangles/ hypercubes although a similar algorithm can do so.

am not aware of this published in the literature but its not complex and presumably it is cited somewhere at least in passing. the literature on this subject generally works with Kd-trees or quadtrees (2d case) and falls in the general category of database range query/ searching. the approach there would generally be to allow general geometric objects to be defined such as polygons and then find all the nodes in the Kd that the polygon overlaps with and do the range computation over all the nodes of the polygon(s) to determine intersections.


Exploring and interpolating a function using machine-learning? Which general machine-learning methods are there that try to "learn" or interpolate a smooth multivariate function and which get to actually choose the points at which the function is evaluated during the learning process (exploration)?

The idea would be that each function evaluation is more or less costly and the algorithm learns to explore the regions of space where the gain of knowledge is greatest (vs. the cost of evaluating the function). The function may be non-analytic (e.g. with kinks) in the most interesting cases.

My background is physics, and I am sure that such methods exist, but despite some searching I could not find something that is directly relevant, possibly because I do not know the right terms to look for. I only know that more broadly speaking 'reinforcement learning' is the area of AI dealing with exploration and rewards, so maybe the methods I am asking for represent some special case of that.

For clarification, here is an example: You might want to get the phase diagram of a substance, i.e. the density as a function of pressure p and temperature T. So we are dealing with a (mostly) smooth function of two variables (p,T). Its evaluation at any given point (p,T) requires an expensive Monte-Carlo simulation (lots of CPU time; how much even depends on where in the p,T-space you are). The ideal algorithm would judiciously pick points (p,T) at which to evaluate the density, trying to go towards regions where the function has the most salient features (e.g. phase transition lines, i.e. non-analyticities). Then afterwards, when you ask the algorithm for the density at any other point (p,T), it provides the best possible interpolation/extrapolation that it can come up with, given all the information it has acquired during its exploratory phase.

I would look into the field of "optimal experimental design" in bayesian inverse problems, particularly the recent work of Alen Alexandrian.

http://arxiv.org/abs/1410.5899

http://www4.ncsu.edu/~aalexan3/research.html

Essentially, one has an inner inverse problem for approximating the function based on point measurements of derived quantities, hosted within an outer optimization problem for choosing the points based on minimizing a combination of the error and the variance.

Furthermore, you don't need to do a full inner-outer solve procedure. Rather, you can use the KKT conditions for the inner problem as the constraint for the outer problem, and formulate a "meta" KKT system for the combined problem.

It is formulated in the language of PDE-constrained inverse problems, but would also apply to simpler situations like your problem (the "PDE" becomes the identity matrix..)

genetic algorithms can be used for this purpose. in some cases the fitness function evaluation is somewhat "expensive". part of the difficulty is encoding some kind of measurement of "interesting regions" and this metric would somehow have to quantify measurements over multiple function evaluations ie a single function evaluation is not enough to "notice a trend". ie:

  the algorithm learns to explore the regions of space where the gain of knowledge is greatest

and later you call it "finding most salient features".
this statement is problematic because it is generally hard to mathematically quantify "where the gain of knowledge is the greatest" or "salient features". one possibility to formalize/ quantify it is to consider "high-entropy vs low-entropy" for which there is a large body of theory.

your problem is also somewhat split along the lines of supervised  vs unsupervised learning so thats an area to further analyze wrt your problem.

a recent major case of successful application of ML in physics was the Higgs machine learning challenge and incorporates many of the ideas you mention. in this case particle track behavior is predicted by the ML algorithm and it automatically learns about noise vs signal in the data. winning algorithms generally used decision trees as described in the paper.


Why hasn't functional programming researched dynamic trees? Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging dictionaries ("A Simple Mergeable Dictionary" by Adam Karczmarz),

By dynamic trees I refer to the definition stated in Sleator & Tarjan's paper "A data structure for dynamic trees" in 1983. Few efforts have been published within the functional programming research area since.

Edward Kmett implemented a version of the ST trees mostly as a translation of the C++ counterpart, see Link-cut trees.
Chris Okasaki wrote a limited implementation of the Splay trees in his renowned book "Purely functional data structures".
Ralf Hinze and Ross Paterson introduced a functional data structure called 2-3 finger trees but with somewhat different aim from that of original definition of dynamic trees.

Implementation (and perhaps performance) of dynamic trees are divided according to three approaches:

Linearization, where ET trees (Euler tour) play a great role. Not found a purely functional study.
Path-decomposition, where ST trees are the flagship, just found the Kmett's version.
Tree contraction, where Top trees, topology trees and RC trees are the players. Not found a purely functional study.

Purely functional analysis and implementation can be found on Splay, AVL, red-black tree, but those are NOT dynamic trees. The former are considered the shadow (also called virtual or auxiliary) data structure of the latter.

So, my question is:

What are the reasons (drawbacks, weaknesses) for the Functional Programming research community not to take part into the dynamic trees data structure?

"In computer science, functional programming is a programming paradigm.  A style of building the structure and elements of computer programs that treats computation as the evaluation of mathematical functions and avoids changing state and mutable data." - Wikipedia

"changing state and mutable data"  in other words "dynamic".

So your question is a bit like asking why left isn't right.


Solving distance-d independent set in a simple way I'm solving distance-d independent set problem, as a follow up to my last question. I'm not quite experienced in a subject, so I'm looking for a simple algorithm (which has to be an exact algorithm). So far I have:

Input: undirected planar grid graph $G$, which might not be "full", but be  a subgraph of a full rectangular grid. Also, a natural numbers K (size of independent set) and L (distance).
Represent graph as a adjacency list (or dictionary of adjacency sets, it should be more efficient), since it's sparse (property of planar grid graphs).
Calculate $G^L$ (graph power) with BFS - $O(V*E)$ (complexity explanation)
Solve independent set problem.

The last one has at least a few solutions:

Find independent set with brute force - $O(2^V * V^2)$
Calculate complement of $G$ in polynomial time (I think $O(V+E)$, but I'm not sure) and check if it contains a clique of size $K$, e. g. with brute force, which for fixed K is polynomial - $O(V^K * K^2)$
Since Independent Set and Vertex Cover problems are complementary, find Vertex Cover of size $V - K$; there exists simple algorithm with complexity $O(1.47^{VC size}$) - $O(1.47^{V - K})$

My questions (simple = understandable and "code-able" in less than 1 day for an undergraduate student):

Am I missing something here altogether and should I go other route, without calculating $G^L$, e. g. vertex coloring?
Is there a simple direct independent set algorithm better than brute force?
Am I right that VC is straight up better than brute force clique here?
Wikipedia article on clique problem states that maximum clique can be found by simple enumeration in $O(1.4422^n)$. For my fixed size k, can this bound be tightened? If so, how should I modify the clique enumeration algorithm? Or is there a simpler way?

I'm sorry although I prefer to think of simple answers, ur Q triggers in my mind addressing other problems (a level of a research topic not an under graduate task)

Anyways, here is what popped up in my mind just incase u find something inspiring in them

-About the Kth Largest Subset problem http://dx.doi.org/10.1016/j.ipl.2015.09.015

-About Goemetric Set Packing problem
(I myself didn't study it a lot, but read some papers about it when someone suggested it to me. I did not use it in my work, but the way u r trying to describe ur problem tells it has a Goemetric landscape nature so maybe it will be useful for u)

https://www.sciencedirect.com/science/article/pii/S0925772112000740

https://slideplayer.com/slide/4514539/

I have more resources if u need so

.

Finally, u may search for exact MWIS algorithms and u'll find a lot. Here is one paper
"Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs", Sebastian Lamm
, Christian Schulz, Darren Strash, Robert Williger, Huashuo Zhangk.
arXiv:1810.10834v1 [cs.DS] 25 Oct 2018


turing machine for the language L ={w#w' where w<w'} I'm blocked with a question for a long time.

L ={X=w#w' where w < w' and w,w' in {0,1}* }

So i'm trying to find :

1-a deterministric turing maching for the language L.

2-a non deterministic for L.

example :

      w=01 w'=111 --> X in L.

      w=1 w'=011 -->  X is **not** in L.

For the deteministic machine , i have an idea only when |w|=|w'|, it's only comparing an alphabet in the first word with an alphabet in the second word.

but i don't know how to solve it when we have two different length ; like my second example .

Do you have any idea for the turing machine?

Thank you.

Here is a sketch of a construction method of the TM:

Compare bit by bit from the first bit to the last bit as normal. If equals, proceed to the next bit. Otherwise, it can decide the order.
If the head of TM reaches the word separator $\#$ or the blank symbol (say $\$$ or something), finish the comparison. If both words end simultaneously (i.e. when $\left| w \right| = \left| w' \right|$), then $w = w'$. If not, the shorter word is less than the other in the lexicographic order.

This idea is the same for both a deterministic TM and a non-deterministic TM. Only a non-deterministic TM can compare bits in a non-deterministic way.

First, you can compute $|w|$ and $|w'|$. For the minimum between of them, proceed with your algorithm, comparing bit by bit. If they equal for all the bits, the longer one is the "greater" and then you can decide if the given word belongs to $L$.


Using Dijkstra's algorithm with negative edges? Most books explain the reason the algorithm doesn't work with negative edges as nodes are deleted from the priority queue after the node is arrived at since the algorithm assumes the shortest distance has been found. However since negative edges can reduce the distance, a future shorter distance might be found; but since the node is deleted it cannot be updated.

Wouldn't an obvious solution to this be to not delete the node? Why not keep the node in the queue, so if a future shorter distance is found, it can be updated? If I am misunderstanding the problem, what is preventing the algorithm from being used with negative edges?

Short answer is that Dijkstra is a greedy algorithm, meaning we assume that we have made the best choice possible in every step of the algorithm. With negative edges, this is no longer possible and thus a greedy algorithm will not suffice.

Here's an analogy: (that might help, or confuse even more) Take a convex optimization problem and poke a concavity into it. Now ask the question why it can't be solved with a linear program. The problem is that the linear program's premise is that once we reach the edge of a convex surface in the direction of optimality, we know for certain it is optimal. With a concavity, this no longer works and the algorithm falls flat. The negative values are like these concavities, they introduce local extrema making it harder to find the global one.

For Dijkstra's Algorithm, at every step, the visited node, v, is done and never visited again (invariant) , the edge to that node v is the min edge.

To show why Dijkstra's Algorithm would not produce a optimized shortest path, let's take this graph with negative edge (A, B) as an example, at the start there are S (source node), A, B, C, D.

Starting at source node S, we would choose the edge (S, B) as the edge weight is shorter.
Node is would be marked done and the edge (S, B) would be set as the min edge from S to B.
Since Dijkstra is a greedy Algorithm, node B is visited and would never be visited again.

But there is a shorter path from S -> A -> B of weight 0. Dijkstra would provide a wrong path since it might not be considered due to the invariant of the algo.

  Wouldn't an obvious solution to this be to not delete the node? Why not keep the node in the queue, so if a future shorter distance is found, it can be updated?

It would be slower, keep it only if you need to. If you do that, you are essentially writing the Bellman Ford Algorithm, so I would refer address it as the Bellman Ford Algorithm. It is the original shortest path algorithm.
Assume a graph of V vertices and E edges.
Note that Dijkstra $ O((V + E) log V) $, is slightly faster than Bellman Ford $ O (VE) $, as it is a optimized version of Bellman Ford.

i. Dijkstra is faster than Bellman Ford due to it's invariant. It would only visit each vertex once and the edges it checks would reduce as vertex visited increases, since it assumes the edges it sets would be the best path. Whereas,

ii. Bellman Ford algorithm would run the relax function for V times on E edges. It works by overestimating the length of the path from the starting vertex to all other vertices. Then it iteratively relaxes those estimates by finding new paths that are shorter than the previously overestimated path. After 1 iteration of relaxing E edges, one edges is the best path.

So if you correctly tweak the program to keep the edge, it would be slower. In algorithm, you often have to trade time and function, time and space, it depends on you.


How to prove the following xor equation? In a test paper, a question is given as :

Let, x1^x2^x3^x4 =0 where x1, x2, x3, x4 are Boolean variables,and ^ is the XOR operator.

Which one of the following must always be TRUE?
(A) x1x2x3x4 = 0
(B) x1x3+x2 = 0
(C)  x1'^x3' = x2'^x4'
(D) x1+x2+x3+x4 = 0

+ is OR and concatenation is AND operator.

Correct answer is C, which I guessed because when all booloean variables are 1, then, neither A,B, or D will hold,But what is the correct way to get to option C?

(I use the symbol $\oplus$ here because $\wedge$ is mathematically used for conjunction ("and") instead of exclusive-or)

First we rearrange the terms,
\begin{align}
 x_1 \oplus x_2 \oplus x_3 \oplus x_4 &= 0 \\
 x_1 \oplus x_3 \oplus x_2 \oplus x_4 &= 0 \\
 x_1 \oplus x_3 &= x_2 \oplus x_4
\end{align}
Then use $a \oplus b = a' \oplus b'$ to get (C).
$$ x_1' \oplus x_3' = x_2' \oplus x_4' $$

Xor means when we get two same variables answer is 0. That is 0^0=0 and 1^1=0. it is possible to get x1^x2^x3^x4=0 if and only if x1^x2==x3^x4


Balancing subproblems in resilience testing You’re doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder with $n$ rungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung.
It might be natural to try binary search: drop a jar from the middle rung, see if it breaks, and then recursively try from rung $n/4$ or $3n/4$ depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer.

If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar—at the moment it breaks, you have the correct answer—but you may have to drop it $n$ times (rather than $\log n$ as in the binary search solution).

So here is the trade-off: it seems you can perform fewer drops if you’re willing to break more jars. To understand better how this trade- off works at a quantitative level, let’s consider how to run this experiment given a fixed “budget” of $k \ge 1$ jars. In other words, you have to determine the correct answer—the highest safe rung—and can use at most $k$ jars in doing so.

Suppose you are given a budget of $k = 2$ jars. Describe a strategy for finding the highest safe rung that requires you to drop a jar at most $f (n)$ times, for some function $f (n)$ that grows slower than linearly. (In other words, it should be the case that $\lim_{n\to\infty} f (n)/n = 0$.)

Anyone any insights how to solve this problem?

I know that the answer is $h = \sqrt n$. I know  that it solves the problem. But I want to know how you got that answer, there must be a general way to do it?

Drop the first jar at the $\sqrt{n}$th rung, $2\sqrt{n}$th rung, and so on until it breaks at the $m\sqrt{n}$th rung. (This takes at most $\sqrt{n}$ steps). Then drop the second jar at every rung between the $(m-1)\sqrt{n}$th rung and the $m\sqrt{n}$th rung until you find the precise breakpoint.

for k equal to 2
first drop the jar from the second rung if it breaks the safe rung is 1st rung else then drop it from 5th rung if it breaks then the safe rung lies below it and come one rung down and drop another jar if it breaks again then the safe rung is the below one else this is the safe rung you can repeat this process again and again till u find the safe rung with the help of this stratergy at the expense of k equal to 2 rungs we will find the maximum safe rung with higher efficiency


unambiguous grammar that produce equal number of a and b is there any unambiguous grammar on alphabet={a,b} that can produce strings which have equal number of a and b (e.g. "aabb" , "baba" , "abba") ?

The problem with $S\to aSbS\mid bSaS\mid \varepsilon$ is that you're just making sure you match each $a$ with a $b$ (where we consider an $a$ and a $b$ to be matched iff they appeared during the same derivation step).

To ensure non-ambiguity, you must add a constraint on the matching to ensure that it is unique (while maintaining its existence). One way to do that is to make sure you match the first $a$ (resp. $b$) after your $b$ (resp. $a$) that hasn't been matched yet.

So you'd get something like $$
S\to aB S\mid bA S \mid \varepsilon\\
A \to a \mid b \square\\
B\to b \mid a\square$$

The idea is the following:

You want $S$ to generate words with as many $a$ as $b$s. At any points you can stop with the $S\to \varepsilon$. If you do add an $a$ with $S\to aBS$, then you need to add a $b$ later, and you put a $B$ to remind you of that, and then you continue with another $S$. The same things applies for $S\to bAS$.
If you have an $A$, it means that you are one $a$ short. If you read an $a$, everything is fine and you've got nothing else to do. But if you read a $b$, you are now two $a$s short. I left a $\square$ for you to fill to encode that.
$B$ works like $A$.

Solution :

   You are two $a$s short so you are twice one $a$ short: $A \to a \mid b AA$. Similarly $B\to b\mid aBB$

For the proof, see this where $a,b,A,B$ are replaced with $0,1,O,I$ and your language is generated by $E$.

The ambiguity of the above grammar can be resolved as

S->aBS/bAS/ε
A->a/bAA
B->b/aBB


What is the significance of negative weight edges in a graph? I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles.

So, I wonder what's the real world significance of negative weight edges? A plain English explanation would be helpful.

Saeed Amiri has already given an excellent example in a comment: the weight on edges can represent anything in the real world, for example, the amount of money to be transferred from one account to another account. The amounts can be positive or negative. For example, if you want to go from $a$ to $b$ in your graph while losing as less money as possible (shortest path), then you can consider negative weights. For more, see this book chapter.
Apart from that, there are many more applications. The negative weights depend on what you model it to be. For example,
consider this graph

Chemistry: The weights can be used to represent the heat produced during a chemical reaction. (Nodes: compounds, Edge $e_{uv}$: if compound $v$ can be obtained ("chemically reduced") from $u$). In this graph: you produce $4$ kJ to convert $s$ to $a$ and $2$ kJ to convert $a$ to $t$. You need $5$ kJ to get back $s$ from $t$.

Real Life: Think of a driver, who gets paid to drive his employer from $s$ to $t$ but he pays between $a$ and $b$ (say traveling between his home and his workplace).

Games: Suppose you play rock-paper scissor for money. Nodes: rock, paper, scissors. Edges: any relation (clique). Weights: wager. In this graph: (forget about $b$), here, $s$ beats $a$, $a$ beats $t$ and $t$ beats $s$, and wins 4,2,-5 respectively.

Traffic congestion on a map:

One other real world example of associating weights to an edge could be the weights represent traffic conditions in a map (more negative, more unfavorable) - we could then use this representation to compute optimal distances.

We can really use the "weight" metaphor to represent anything of positive/negative value between any two points in a graph


Internal and External Fragmentation I am working over a homework problem and am confused on how to determine whether there is internal and external fragmentation given the following table:

Characteristic                   Design 1 Design 2 Design 3
Physical Memory Address Width:     8 bit    16 bit   32 bit
Virtual (Logical) Address Width:   12 bit   20 bit   24 bit
Page/Frame size in bytes:          16 bytes 32 bytes 64 bytes

More specifically, which design has the most internal fragmentation and external fragmentation and why?

I have found the answer. External fragmentation happens over time when small spaces in memory are not effectively employed. This leads to hole everywhere in memory. Therefore it cannot be determined from the chart that there is external fragmentation.

On the other hand, internal fragmentation is the idea when there is over-allocation of memory space to a process. In the above chart, internal fragmentation depends on the page/frame size. Since it is possible for a page to only have one byte of data then larger page sizes have more internal fragmentation. Design 3 has the most spread which is the answer.

I know that external fragmentation occurs by memory problem, when we have less memory space in mvt partition (multiprogramming with variable no. of task) called external frag..

when we have less memory space in mft partition (multiprogramming with fixed no. of tasks) called internal frag....


Relational query for universally quantified formula My university is participating in the implementation of a library borrowing managing system at Richelieu National Library in France.

I received the order to formulate the query: "find all users having borrowed every book" in relational Algebra, in relational Calculus and in SQL (which would probably not happen, probably librarians want to test the limits of the database).

The database has the following pattern (the primary keys are in bold):

Borrowing(People, Book, DateBorrowing, ExpectedReturnDate, EffectiveReturnDate)
Lateness(People, Book, DateBorrowing, LatenessFee)

I tried

$$\Pi_{People}(Borrowing)\div\Pi_{People}(\sigma_{Book} (Borrowing))$$

But It seemed to be wrong as far as to do  $r\div s$, $S\subseteq R$  is needed, which seems not to be the case, but why? I'm still talking about people, isn't it?

I then tried the following relational calculus formula:

$$\{t.People|Borrowing(t)\wedge(\forall u Borrowing(u)\Rightarrow t.DateBorrowing)\}$$

To find every books that have a borrowing date. I know this calcuation is false but I don't know how to do better...

Then in SQL:

SELECT People FROM Borrowing
    WHERE FORALL Books EXISTS DateBorrowing

That is what I tried and I know that is not the right way to "find all users having borrowed every book". Can you help me expressing correctely such a querry?

SQL does not have a universal quantifier, but an equivalent can be constructed from the existential one, through a normalization process similar to Skolemization: $$\forall x P(x) \iff \nexists x \neg P(x)$$

In your case, you want the users for which there does not exist a book that they have not borrowed:

select * from people p
where not exists
  (select * from books b
   where b.id not in
     (select book_id
      from borrowings
      where people_id=p.id)
  )

(Note that I have assumed tables for people and books to represent their existence separately from the borrowings table, which, for instance, may be empty at the inception of the system.)

select distinct people
from borrowing
group by people
having count(book) in (select count(book) from borrowing);


Canonical representation of programs I'm working on some compiler software, and I'm looking for information on canonical forms for expressing software, algorithms, mathematical expressions (including predicate logic), etc. I assume canonicalization is generally intractable, but NP algorithms and more-constrained problems (e.g. pure functions) are also interesting. Normal forms may be useful too. My goal is not to be able to represent and manipulate all programs, but some of them (the trivial ones).

The brief survey contained in this paper might be of interest:

J. Swan, Z. A. Kocsis, and A. Lisitsa. 2014. The 'representative' metaheuristic design pattern. In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO Comp '14). ACM, New York, NY, USA, 1435-1436. DOI=http://dx.doi.org/10.1145/2598394.2609842.

It discusses the existence of canonical forms for various forms of representation (groups, rings, boolean functions etc) and in particular normal forms for the lambda calculus using $\beta$-reduction as a rewrite rule.

this general area fits into the concept/ subarea of intermediate representations/ IRs. here are some basic overviews/ surveys/ refs to start. another related area with large theory is bytecodes. there is some analysis of "canonicalization" of IRs but it is possibly or probably not a major focus in compiler design because, as you say, its undecidable in general. the more practical/ common approach is apparently a "normalizing" or "best-attempt/ heuristic streamlining" of the IRs. a technique that has seen major applied advancement in recent times is just-in-time compiling eg in Java hotspot/ Javascript (v8 engine).

The Challenge of Cross-language Interoperability: The increasing significance of intermediate representations in compilers / Chow
Lecture Notes on Intermediate Representation / Pfenning
NORMAL FORM FOR COMPILER TESTING / Hanan Samet


Water Jug Problem in AI In AI we can classify a problem in 3 classes,  ignorable, recoverable or irrecoverable problems. Now while reading Water jug Problem

I am wondering in which of these 3 class it should fall? It should reside under recoverable right? As we can go back to the previous state in Water Jug Problem by altering the water level, I think it is recoverable. Is my thinking right?

Recoverable, as we can pour all water back to the 12L jug to restore the original state, hence any state derived thereof (by following the same steps from the start). The problem is, also, solvable:

[12, 0, 0]
[4,  8, 0]
[4,  3, 5]
[9,  3, 0]
[9,  0, 3]
[1,  8, 3]
[1,  6, 5]
[6,  6, 0]  # <-- SOLVED; 7 steps

DETAILS: The problem stated as-is is recoverable, and in a machine learning problem statement, we take the problem as-defined, not how it could be defined. For any # of jugs of any sizes, as long as we start with only one jug filled, the entire system is recoverable - but if more than one jugs are filled, that changes the entire problem, and can make it irrecoverable.

[0, 0, ..., X,   ..., 0] <-- only one jug filled
[2, 0, ..., X-2, ..., 0]
...
[2, 4, ..., ?,   ..., 7] <-- some arbitrary state
...
[0, 0, ..., X,   ..., 0] <-- RECOVERED; empty all other jugs into original jug

Update: the system is also recoverable if starting with any # of jugs filled, as long as they're fully filled. They also don't necessarily have to be fully filled, but it then becomes jugsize-dependent, and no generalization w/o mathematical formulation can be made.

DEFINITIONS: OP hasn't defined "recoverable", "irrecoverable", or "ignorable" - and neither Google nor DuckDuckGo reveal much. Giving my best attempt at making sense of it, each can be defined as follows:

Recoverable: state t0 can be restored from any other state T when starting at t0
Irrecoverable: there exists some state T we can get to from t0, but no longer revert to t0
Ignorable: we don't care, and can solve the problem at hand either way

Irrecoverable example: [0, 1, 2] --> [0, 0, 3]. Goodbye forever, 1 liter & 2 liters.

Ignorable example: goal: two jugs empty. In this case, both the original [12, 0, 0] and the irrecoverable case [0, 1, 2] work.

In Recoverable method:
12lit.   8lit.   5lit.
 ( 4 ,        8,         0)
 ( 4,         3,         5)
 ( 9,         3,         0)
 ( 1,         8,         3)
 ( 1,         6,         5)
 ( 6,         6,         0) //step 6 Splited.
In step 6,you can split up the water to give away exactly 6 litres and keep 6 litres


What are common techniques for reducing problems to each other? In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as some other problem $L_2$ by mapping instances from $L_2$ to solution-equivalent ones in $L_1$. Essentially, we show that any solver for $L_1$ can also solve $L_2$ if we allow it to use the reduction function as preprocessor.

I have performed my share of reductions over the years, and something keeps bugging me. While every new reduction requires a (more or less) creative construction, the task can feel repetitive. Is there a pool of canonical methods?

What are techniques, patterns and tricks one can regularly employ for constructing reduction functions?

This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

The Special Case

Assume we want to show $L_1 \leq_R L_2$ with respect to some notion of reduction $R$. If $L_1$ is a special case of $L_2$, that is quite trivial: we can essentially use the identity  function. The intuition behind this is clear: the general case is at least as hard as the special case.

In "practice", we are given $L_2$ and are stuck with the problem of picking a good reduction partner $L_1$, i.e. finding a special case of $L_2$ that has proven to be $R$-hard.

Simple Example

Assume we want to show that KNAPSACK is NP-hard. Luckily, we know that SUBSET-SUM is NP-complete, and it is indeed a special case of KNAPSACK. The reduction

$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$

suffices; $(V,W,v,w)$ is the KNAPSACK instance that asks whether we can achieve at least value $v$ with item values in $V$ so that the corresponding weights from $W$ remain beneath $w$ in total. We don't need the weight restrictions for simulating SUBSET-SUM, so we just set them to tautological values.

Simple exercise problem

Consider the MAX-3SAT problem: given a propositional formula $\varphi$ and integer $k$, decide whether there is an interpretation of $\varphi$ that fulfills at least $k$ clauses. Show that it is NP-hard.

   3SAT is a special case; $f(\varphi) = (\varphi, m)$ with $m$ the number of clauses in $\varphi$ suffices.

Example

Assume we are investigating the SUBSET-SUM problem and want to show that it is NP-hard.

We are lucky and know that the PARTITION problem is NP-complete. We confirm that it is indeed a special case of SUBSET-SUM and formulate

$\qquad \displaystyle f(A) = \begin{cases}
  \left(A, \frac{1}{2}\sum_{a \in A} a\right) &, \sum_{a \in A} a\mod 2 = 0 \\
  \left(A, 1 + \sum_{a \in A} |a|\right) &, \text{else}
\end{cases}$

where $A$ is the input set of PARTITION, and $(A,k)$ is an instance for SUBSET-SUM that asks after a subset of $A$ summing to $k$. Here, we have to take care of the case that there is no fitting $k$; in that case, we give an arbitrary infeasible instance.

Exercise Problem

Consider the problem LONGEST-PATH: given a directed graph $G$, nodes $s,t$ of $G$ and integer $k$, decide whether there is a simple path from $s$ to $t$ in $G$ of length at least $k$.

Show that LONGEST-PATH is NP-hard.

   HAMILTON-CYCLE is a well-known NP-complete problem and a special case of LONGEST-PATH; $f(G) = (G,v,v,n)$ for arbitrary node $v$ in $G$ suffices.
 Note in particular how reducing from HAMILTON-PATH requires more work.

it depends on the complexity classes involved, and whether one wants to reduce from a given $A$ to an unknown $B$, or an unknown $B$ to a given $A$. the common scenario is to prove problems NP Hard or NP Complete. a common technique is to construct "gadgets" in one domain that behave in a certain way, mimicking the behavior of another domain. for example to convert SAT to vertex cover, one constructs "gadgets" in vertex cover that behave similarly to clauses of SAT, eg in the following slide show: NP Complete reductions by Krishnamoorthy (also with an example for Hamilton path).

a useful strategy is to work from large compilations of problems from the complexity class in question and find the "apparent nearest problems" to the problem being studied. an excellent reference along these lines is Computers and Intractability, a guide to the theory of NP completeness, Garey and Johnson organized by different problem types.


How to calculate the number of tag, index and offset bits of different caches? Specifically:

1) A direct-mapped cache with 4096 blocks/lines in which each block has 8 32-bit words. How many bits are needed for the tag and index fields, assuming a 32-bit address?

2) Same question as 1) but for fully associative cache?

Correct me if I'm wrong, is it:

  tag bits = address bit length - exponent of index - exponent of offset?

  [Is the offset = 3 due to 2^3 = 8 or is it 5 from 2^5 = 32?]

The question as stated is not quite answerable.  A word has been defined to be 32-bits.  We need to know whether the system is "byte-addressable" (you can access an 8-bit chunk of data) or "word-addressable" (smallest accessible chunk is 32-bits) or even "half-word addressable" (the smallest chunk of data you can access is 16-bits.)  You need to know this to know what the lowest-order bit of an address is telling you.

Then you work from the bottom up.  Let's assume the system is byte addressable.

Then each cache block contains 8 words*(4 bytes/word)=32=25 bytes, so the offset is 5 bits.

The index for a direct mapped cache is the number of blocks in the cache (12 bits in this case, because 212=4096.)

Then the tag is all the bits that are left, as you have indicated.

As the cache gets more associative but stays the same size there are fewer index bits and more tag bits.

in full associate mapping index is 0 b/s like you say set = 1
so index=log of 1 in base 2 =0
set offset =log of block size of byte base 2 so use 8=2^3 or 32=2^5
tag=32-0-5=27
for direct
index=2^12=12
offset=0
bit tag= 32-12-0=20


Minimum XOR for queries I was asked the following question in an interview.

Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \otimes b$ is minimum, where $x\otimes y$ for to integers $x$ and $y$ is the bitwise xor operation of $x$ and $y$.

For example:

Input:

A = [3, 2, 9, 6, 1]
B = [4, 8, 5, 9]

Output

[6, 9, 6, 9]

Because when 4 is XORed with any element in A minimum value will occur when A[I] = 6

4 ^ 3 = 7
4 ^ 2 = 6
4 ^ 9 = 13
4 ^ 6 = 2
4 ^ 1 = 5

Here is my brute force solution in python.

def get_min_xor(A, B):

    ans = []

    for val_b in B:
        min_xor = val_b ^ A[0]

        for val_a in A:
            min_xor = min(min_xor, val_b ^ val_a)
            # print("{} ^ {} = {}".format(val_b, val_a, val_b ^ val_a))

        ans.append(min_xor ^ val_b)

    return ans

Any ideas on how this could be solved in sub O(MxN) time complexity?

I had the following idea in mind.
I would sort the array A in O(NlogN) time then for each element in B. I would try to find it's place in the array A using binary search.Let's say B[X] would fit at ith position in A then I would check the min XOR of B[X] ^ A[i-1] and B[X] ^ A[i+1]. But this approach won't work in all the cases. For example the following input

A = [1,2,3]
B = [2, 5, 8]

Output:

[2, 1, 1]

Here is the trie based solution

class trie(object):
    head = {}

    def convert_number(self, number):
        return format(number, '#032b')

    def add(self, number):
        cur_dict = self.head

        binary_number = self.convert_number(number)

        for bit in binary_number:

            if bit not in cur_dict:
                cur_dict[bit] = {}
            cur_dict = cur_dict[bit]

        cur_dict[number] = True

    def search(self, number):
        cur_dict = self.head

        binary_number = self.convert_number(number)

        for bit in binary_number:
            if bit not in cur_dict:
                if bit == "1":
                    cur_dict = cur_dict["0"]
                else:
                    cur_dict = cur_dict["1"]
            else:
                cur_dict = cur_dict[bit]

        return list(cur_dict.keys())[0]

def get_min_xor_with_trie(A,B):

    number_trie = trie()

    for val in A:
        number_trie.add(val)

    ans = []

    for val in B:
        ans.append(number_trie.search(val))

    return ans

Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values).

Let say we know that all integers in $A$ are 32-bit values. Use the following steps:

Create an empty trie. Every node of trie may contains at most two children
for 0 and 1 bits.
Insert all values in $A$ into the tree in $O(32 \times m) = O(m)$
For each value in $B$, traverse the tree from the leftmost bit. If a bit doesn't match with child of a middle node, continue the traverse using the existing child until you reach a leaf. Traversing finishes in $O(32 \times n) = O(n)$

Which in total, the complexity is $O(m + n)$.

Using Trie Data Structure.

public class Solution {

    public int[] solve(int[] A, int[] B) {
        int ans[] = new int[B.length];
        Trie root = new Trie();
        for (int s : A) {
            insert(root, s);
        }
        for (int i = 0; i < B.length; i++) {
            ans[i] = search(root, B[i]);
        }
        return ans;
    }

    class Trie {
        public Trie left, right;
        public int val;

        public Trie() {
            left = right = null;
            val = Integer.MIN_VALUE;
        }
    }

    public void insert(Trie t, int n) {
        Trie root = t;
        for (int pos = 31; pos >= 0; pos--) {
            int bit = (1 << pos) & n;
            if (bit == 0) {
                if (t.left == null) {
                    t.left = new Trie();
                }
                t = t.left;
            } else {
                if (t.right == null)
                    t.right = new Trie();
                t = t.right;
            }
            if (pos == 0)
                t.val = n;

        }
    }

    private int search(Trie t, int n) {
        // TODO Auto-generated method stub
        Trie root = t;
        for (int pos = 31; pos >= 0; pos--) {
            int bit = (1 << pos) & n;
            if (bit == 0) {
                if (t.left != null)
                    t = t.left;
                else
                    t = t.right;

            } else {
                if (t.right != null)
                    t = t.right;
                else
                    t = t.left;
            }
            if (pos == 0)
                return t.val;
        }
        return 0;
    }
}


What does big O mean as a term of an approximation ratio? I'm trying to understand the approximation ratio for the Kenyon-Remila algorithm for the 2D cutting stock problem.

The ratio in question is $(1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$.

The first term is clear, but the second doesn't mean anything to me and I can't seem to figure it out.

The expression "$A(L) \le (1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$" is, as usual, shorthand for the following:

  There exist constants $c>0$ and $\varepsilon_0>0$ such that for all $\varepsilon$ with $0<\varepsilon<\varepsilon_0$, the inequality $A(L) \le (1 + \varepsilon) \text{Opt}(L) + c/\varepsilon^2$ holds.

are you looking for explanation on Big O? if Yes, this link might help you
http://en.wikipedia.org/wiki/Big_O_notation


Best introductory "algorithms"/"more than just coding" comp sci book? I've been programming in languages (C/C++/Ruby/Java/HTML) for some time now and am currently entering my senior year of high school. I'm taking AP Comp Sci, which uses Java, but want to have a better grasp of some of the more "math-y" concepts in computer science, like hashes/algorithms/etc. For someone who has done basic object oriented programming but doesn't know any of the algorithmic aspects of computer science (And wants to know them before he goes off to college), what books would you recommend that cover algorithms and the more mathematical stuff in a way that's easy for your rudimentary programmer to understand?

Some examples I've heard given are "Introduction to Algorithms" and "Structure and Interpretation of Computer Programs"; I was going to go with Introduction to Algorithms but it's around 80 dollars new, and I'm not sure if SICP has any of the algorithmic math I want to pursue. Haha, I guess all I'm asking for is personal opinions from people that have studied algorithm books and can give honest personal opinions.

Any and all feedback is appreciated; Thank you!

-Neil

Check out From Mathematics to General Programming by Alexander Stepanov and Daniel E. Rose.

Beginning with the basics of number theory you progress up to dealing with content that is typically covered in a 3/400 level abstract algebra course (depending on the institution).


Are turing machine really countable? I feel the notion "there are countably many Turing machines" is wrong.
Suppose there is a Turing machine whose input alphabet is {0}. If we replace the input alphabet {0} with {a} and replace every occurrence of "0" with "a" in the transition table, then we get another Turing machine. Obviously, these two machines are different beacause they recognize different languages, but using any one reasonable encoding sheme, they could be encoded into the same string. So claiming Turing machines are countable only by enumerating their encodings is wrong, because actually there isn't a bijection between Turing machines and their encodings.
Is my opinion right?

You are technically right. The correct phrasing should be that there are countably many TMs up to isomorphism of the tape alphabet and the state-space.

Indeed, if you say that a TM with states $\{q,r\}$ is different than the same TM with states named $\{1,2\}$, then not only are TMs not a countable collection, they are not even a set in the ZFC axiom system.
This follows from the fact that the collection of all sets is not a set itself.

I believe neither of the other two answers are correct, they are falling prey to the same logical mistake : that there are

"uncountably many labels this way"

in the collection of subsets of $\mathbb{N}$.
However, only finite subsets should count. If the subset/language is finite, (or even finitely describable,) there are only countably many of them. See Wikipedia
in particular: this sentence.

Theorem: The set of all finite subsets of the natural numbers is countable.

So

Indeed, if you say that a TM with states {q,r} is different than the same TM with states named {1,2}, then not only are TMs not a countable collection, they are not even a set in the ZFC axiom system.

is wrong.
The way I like to think of countable is

If every element of the set can be theoretically written down unambiguously in a large enough finite book, then the set is countable. This should be self evident:)

Examples:

The set of rationals. Every rational can be written down finitely.
The set of algebraic numbers. Every algebraic number can be described by writing out the equation along with a number and an ordering scheme to define which value is meant.(I.e $x^2=0$ has both $x=\sqrt{2}$ and  $x=-\sqrt{2}$.)

So unless you are using languages that cannot be defined finitely and therefore shouldn't count, your set of Turing machines is still countable.
If anyone can think of a reason why a machine that fails this test of "finitely describable" should count in a set of Turing machines when it can't be built and run, I'd be happy to hear about it.


Why, really, is the Halting Problem so important? I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine with finite memory will either halt or repeat a previous state. You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1).
It seems to me that the Halting Problem proof is nothing more than a so-called "paradox," a self-referencing contradiction in the same way as the Liar's paradox. The only conclusion it makes is that the Halting Function is susceptible to such malformed questions.
So, excluding paradoxical programs, the Halting Function is decidable. So why do we hold it as evidence of the contrary?
4 years later: When I wrote this, I had just watched this video (update: the video has been taken down). A programmer gets some programs, must determine which ones terminate, and the video goes on to explain that it's impossible. I was frustrated, because I knew that given some arbitrary programs, there was some possibility the protagonist could prove whether they terminated. I knew many real-life algorithms had already been formally proven to terminate. The concept of generality was lost somehow. It's the difference between saying "some programs cannot be proven to terminate," and, "no program can be proven to terminate." The failure to make this distinction, by every single reference I found online, was how I came to the title for this question. For this reason, I really appreciate the answer that redefines the halting function as ternary instead of boolean.

Because a lot of really practical problems are the halting problem in disguise. A solution to them solves the halting problem.

You want a compiler that finds the fastest possible machine code for a given program? Actually the halting problem.

You have JavaScript, with some variables at a high security levels, and some at a low security level. You want to make sure that an attacker can't get at the high security information. This is also just the halting problem.

You have a parser for your programming language. You change it, but you want to make sure it still parses all the programs it used to. Actually the halting problem.

You have an anti-virus program, and you want to see if it ever executes a malicious instruction. Actually just the halting problem.

As for the wikipedia example, yes, you could model a modern computer as a finite-state machine. But there's two problems with this.

Every computer would be a different automaton, depending on the exact number of bits of RAM. So this isn't useful for examining a particular piece of code, since the automaton is dependent on the machine on which it can run.
You'd need $2^n$ states if you have n bits of RAM. So for your modern 8GB computer, that's $2^{32000000000}$. This is a number so big that wolfram alpha doesn't even know how to interpret it. When I do $2^{10^9}$ it says that it has $300000000$ decimal digits. This is clearly much to large to store in a normal computer.

The Halting problem lets us reason about the relative difficulty of algorithms. It lets us know that, there are some algorithms that don't exist, that sometimes, all we can do is guess at a problem, and never know if we've solved it.

If we didn't have the halting problem, we would still be searching for Hilbert's magical algorithm which inputs theorems and outputs whether they're true or not. Now we know we can stop looking, and we can put our efforts into finding heuristics and second-best methods for solving these problems.

UPDATE: Just to address a couple of issues raised in the comments.

@Tyler Fleming Cloutier: The "nonsensical" problem arises in the proof that the halting problem is undecidable, but what's at the core of undecidability is really having an infinite search space. You're searching for an object with a given property, and if one doesn't exist, there's no way to know when you're done.

The difficulty of a problem can be related to the number of quantifiers it has. Trying to show that there exists ($\exists$) an object with an arbitrary property, you have to search until you find one. If none exists, there's no way (in general) to know this. Proving that all objects ($\forall$) have a property is hard, but you can search for an object without the property to disprove it. The more alternations there are between forall and exists, the harder a problem is.

For more on this, see the Arithmetic Hierarchy. Anything above $\Sigma^0_0=\Pi^0_0$ is undecidable, though level 1 is semi-decidable.

It's also possible to show that there are undecidable problems without using a nonsensical paradox like the Halting problem or Liars paradox. A Turing Machine can be encoded using a string of bits, i.e. an integer. But a problem can be encoded as a language, i.e. a subset of the integers. It's known that there is no bijection between the set of integers and the set of all subsets of the integers. So there must be some problems (languages) which don't have an associated Turing machine (algorithm).

@Brent: yes, this admits that this is decidable for modern computers. But it's decidable for a specific machine. If you add a USB drive with disk space, or the ability to store on a network, or anything else, then the machine has changed and the result doesn't still hold.

It also has to be said that there are going to be many times where the algorithm says "this code will halt" because it the code will fail and run out of memory, and that adding a single extra bit of memory would cause the code to succeed and give a different result.

The thing is, Turing machines don't have an infinite amount of memory. There's never a time where an infinite amount of symbols are written to the tape. Instead, a Turing machine has "unbounded" memory, meaning that you can keep getting more sources of memory when you need it. Computers are like this. You can add RAM, or USB sticks, or hard drives, or network storage. Yes, you run out of memory when you run out of atoms in the universe. But having unlimited memory is a much more useful model.

I’m not going to address the math or science, except to say it proves we can’t do a whole bunch of things and that there are even more where we can’t say they are solvable until we have solved them.
Instead I’m going to address what seems to be a common emotional reaction to the Halting Problem: that it is a cheap trick like a little boy running around chanting “fooled ya, fooled ya.  I’m rubber, you’re glue whatever bounce off of me sticks to you”.
If the Halting Problem was a song it would be a dirge.  It ends the idea that all problems can be solved with computers. This new toy we had created was not as boundless as it had at first seemed. Some problems are and will remain, forever unsolvable.  What’s even worse, is that in many cases there’s no way to tell the difference between “unsolvable” and “solution not know”, only between “solved” and “unsolvable”.


Decidability. $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$ I'm trying to understand decidable languages. In particular, I would like to show that
$$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \,.\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$
I don't quite understand the process of proving these. I know that $a^kb^k$ is not regular, so then no DFA accepts it. I also know that $A_{DFA}$ (acceptance DFA) is decidable, I also know several other decidable languages like $E_{DFA}$ and $EQ_{DFA}$. How can I use these to prove that $B$ is decidable?

If no DFA accepts $a^kb^k$, doesn't that mean that $A_{DFA}$ will reject? So if $A_{DFA}$ rejects then shouldn't the decider for $B$ accept?

Corollary 3.19 from "An Introduction to the Theory of Computation": "A language is decidable if and only if some nondeterministic Turing machine decides it."

You can construct a nondeterministic Turing machine, $TM_A$, which is a decider for the language : $A_DFA = \lbrace \langle B,w \rangle \mid \text{$B$ is a DFA accepting $w$}\rangle$.

$TM_A$ works as follows on input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is a string:

Simulate $B$ on input $w$.
If the simulation ends in an accept state, accept. If it ends in an non-accepting state, reject.

Update:
The string $a^kb^k$ is not regular and cannot be accepted by a DFA. A CFG for that string would be something like : $A \to aAb \mid \varepsilon$.


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

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

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

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

So basically checking if A+B=C is the decision problem version of the function problem of finding the value of A+B. I guess the decision problem can be solved by subtraction i.e A-C and then comparing the result with B. The circuit for the full subtractor is more complex (having more number of gates) then the full adder. So, finding the addition value is much more easy then checking the addition result.


All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete? My book states this

  If a decision problem B is in P and
  A reduces to B,
  then decision problem A is in P.
  A decision problem B is NP-complete if
  B is in NP and
  for every problem in A in NP, A reduces to B.
  A decision problem C is NP-complete if
  C is in NP and
  for some NP-complete problem B, B reduces to C.

So my questions are

  If B or C is in NP-complete, and all problems in NP reduce to an NP-complete problem, using the first rule, how can any NP problem not be NP complete?
  If A reduces to B, does B reduce to A?

If A reduces to B, does B reduce to A?

No. For a really contrived example, any possible computable problem A is reducible to the Halting Problem: just pass as input the algorithm that solves the problem A but with a while(true) tacked at the end after either the true or false case. However, we know that the Halting problem isn't computable so it can't be reduced to any such algorithm A.

The basic idea is that if there is a reduction from A to B you can learn that B is at least as hard to solve then A and requires an algorithm that is at least as powerful.

So if a problem A reduces to an easy problem B, then we can deduce A is easy (since the reduction gives us the efficient algorithm) and if a hard problem A reduced to a problem B, we can deduce that B is also hard (since if B were easy then A would have to be easy too). However there is still the possibility of making a silly reduction from an easy problem to a hard problem but in this case we can't deduce any conclusions.

I have only the basic idea regarding NPC and NP Problems.
But All i want to comment is about "If A is reduced to B then B is reduced to A? "

Simply consider a set A having {2,3,4,5} elements and set B having {3,4} in it. So A can be reduced to B. But B can't be reduced to A. Instead B can be expanded to A if B gains {2,5} elements.

But if A and B are having the same. then A can be reduced to B or B can be reduced to A.


Why is a quantum computer not capable of solving more problems than a classical computer? On the Wikipedia page for quantum algorithm I read that

  [a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable using classical computers remain undecidable using quantum computers.

I expected that the fundamental changes that a quantum computer brings would lead to the possibility of not only solving problems that could already be solved with a classical computer, but also new problems that could not be solved before. Why is it that a quantum computer can only solve the same problems?

Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each quantum gate modifies those distributions as time progresses. This isn't very efficient (which is why people want to build actual quantum computers) but it works.

One thing that quantum computers should be able to do that regular computers will never do is to use quantum entanglement.

Quantum entanglement is a property that allows to communicate instantly across the whole universe, without transmitting anything. The communication cannot be intercepted or tampered with. Also I can communicate several chips. This means that I can communicate the CPU with the RAM and with the SSD instantly.

So you could have super fast computers. And if I buy some special chip, for example from Amazon Quantum Web Servers, then I could use their infrastructure to perform computations AS IF they were running on my machine... no communication overhead... at least theoretically...

Having a CPU perform all computations in parallel like solving the traveling salesman problem... that makes no sense... if a CPU could do that, all possible results would come out at once... a giant map reduce done in a single chip... how do I pick the right answer?

I mean if the correct answer is 5, but it spells out 5,6,7,8,9,10,15,20,30,40,50,60,70,80... etc. at the same time, how can I know that the correct value is 5?


How to implement two stacks in one array? I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and exercises given in the book by myself.

I am trying to solve Excercise 10.1-2 from Chapter 10 Elementary Data Structures from CLRS Second Edition. Here is what its states:

  Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

The solution that I have come up with so far is:

  Let array A[1..n] implement two stacks: S1[1..i] and S2[i..n].

  For the PUSH-S1 and PUSH-S2 operations, if the stack is 'full' then start pushing elements into the other stack (eg. if stack S1 is full when a new element is trying to be pushed in, then push that element into stack S2 and vice versa).

The problem with this approach is I will not be able to POP-S1 or POP-S2 reliably as there is no way of 'remembering' which element belongs to which stack. If the elements of the stack are (key,value) pairs, the key being the stack number, then to pop an element I would have to search, in the worst case, i or (n-i) times - which will be O(n) (feel free to correct me if I am wrong here), which would not be O(1).

I have been banging my head on the question for quite a while now. Am I on the right track? Can someone give my possible pointers for solving this problem?

In general, how should I 'think' about these problems? Or can only really intelligent people solve these types of problems? Will tackling/solving problems like these (i.e. gaining experience) help me become better at this?

I await enlightenment.

Another hint in addition to what Yuval said: it helps to place the stacks in a specific way in the arrays and fix their direction of growth accordingly. They don't have to grow in the same direction.

Some hints

Make an array

Array elements with odd index are for stack1

Array elements with even index are for stack2

Now You can grow both stacks from left to right direction

Just keep variables that maintain top position of both stacks. You won't have to search the array.

and if stack1 becomes full while stack2 is empty you can keep track for additional stack1 elements in the stack2 by maintaining some variables


NFA to recognize bit strings containing 01111110 Basically, I currently have two ideas but unsure on which is correct for the following question:
"The High level data link control protocol (HDLC), is a popular protocol used for point-to-point data communication. In HDLC, data are organised into frames which begin and end with the sequence 01111110. This sequence never occurs within the main body of the frame, only at the beginning and end (in order to avoid confusion).

a.)Design an NFA which recognises the language of binary strings which contain one or more HDLC frames"

My possible solutions:

The next part is to convert to DFA, but I first need to get this part right.

Might as well go for a DFA directly.

First, recognize the string 01111110. If you see something you don't expect, then the information is malformed and you should enter a dead state.

Once you've seen 01111110, start looking for 01111110 again, but this time, if you see something you don't expect, begin looking for 01111110 again from scratch. Once you see a complete 01111110, you have consumed an entire frame, and you should be in an accepting state.

Then, from this halting state, we add the same transitions we have on our initial state; i.e., we leave open the possibility that there are additional frames. Here's a transition table corresponding roughly to what I've indicated:

  State     Input     New State
  q0        0         q1
  q0        1         dead
  q1        0         dead
  q1        1         q2
  q2        0         dead
  q2        1         q3
  q3        0         dead
  q3        1         q4
  q4        0         dead
  q4        1         q5
  q5        0         dead
  q5        1         q6
  q6        0         dead
  q6        1         q7
  q7        0         q8
  q7        1         dead
  // we've seen the leading 01111110
  q8        0         q9
  q8        1         q8
  q9        0         q9
  q9        1         q10
  q10       0         q9
  q10       1         q11
  q11       0         q9
  q11       1         q12
  q12       0         q9
  q12       1         q13
  q13       0         q9
  q13       1         q14
  q14       0         q9
  q14       1         q15
  q15       0         q16
  q15       1         q8
  // we have now seen the trailing 01111110, a whole frame
  // q16 is the only accepting state.
  q16       0         q2
  q16       1         dead

Naturally, you'll want to check that very carefully. If the goal is outputting the message in between the leading and trailing patterns, you might need some extra states to remember input symbols that may or may not be part of the trailing pattern; but for accepting input which consists of a finite number of valid frames, this (or something close to it, if I've made a silly blunder) should be enough.

Express the language as a regular expression.  Then there is a completely rote method to convert the regular expression to an NFA.  I found a particularly good explanation at http://www.csee.umbc.edu/~squire/cs451_l6.html:

While you can represent r+ as rr*, you can actually add a seventh rule that is just like the r* rule, but leaves out that bottom $\epsilon$ transition:

You can clean up the final NFA at the end by removing any state that has only a single output transition that is also an $\epsilon$ transition.  You remove the source state of the $\epsilon$ transition, and merge all of the inputs of the source state into the destination state of the $\epsilon$ transition.  This often applies to parts of the NFA created by the concatenation rule (rule 5) and the union rule (rule 4).

I think you will get something similar to your second picture, except note that your original problem called for an NFA that recognizes one or more frames.


Is there difference between a function in mathematics to a function in computer science? I never learned a lot of mathematics (generally only arithmetic) and never learned computer science in a formal frame.
I emphasize that I don't mean to ask about a "function" in programming ("procedure"/"method"), rather only about the difference between the formal definition of function in mathematics to the formal definition of function in (theoretical) computer science, if at all there is any such difference (unless computer science don't share the exact definition common in mathematics).
Is there difference between a function in mathematics to a function in computer science?

A function in mathematics is just a special case for a binary relation, where for every x there is exactly one y such that xRy is in the binary relation.
Computer science uses that term with the same meaning, as it uses lots of mathematical terms. It also uses the term "function" (or "subroutine", "procedure", "method") with a totally different meaning of one component of a program in the area of computer programming.
Just like the word "function" would be used with a completely different meaning in patent law (functional vs. decorative components) architecture (a functional design), medicine or psychology (like a "functional alcoholic").

Function in computer science in simple words represents by braces( ) like in c++ we use predefine functions like main() etc but sometimes in ( java) we call this function as method also we have many predefined  functions  in java like substring(),indexOf() and many more but also you will remeber one think these languages also provides controls to declares  your own function
Thanks bro for more reply me i have better command in java ,python and javascript to let me know in which language you want to know the concept of function i will try my best


N subsets with a given sum? How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements?

¹⁾ Not as in $P$, I just want something smarter than $O(n^{|S|})$.

Ex. Let’s say we want $n=3$ subsets with the sum of $K=3$ chosen from $S=[1,1,1,2,2,2]$.

The correct solution is $[1,2], [1,2], [1,2]$.

Ex. Let’s say we want $n=2$ subsets with the sum of $K=5$ chosen from $S=[5,4,3,2,2,2,2,1]$.

One correct solution is $[5], [1,4]$.

Another one would be $[2,2,1], [2,3]$.

Etc. Just a correct solution, regardless of which one.

This problem is strongly NP-hard because it generalizes the 3-Partition problem. That means that it has no efficient (polynomial-time) algorithm, unless P=NP.

Assuming the subsets are disjoint, we first assume we have a blackbox algorithm SUBSET, which given a set $S = [x_1, x_2, x_3,...x_n]$ and an integer $k$, will return a set $T$ such that $T$ is a subset of $S$, i.e $T \subset S$. Given a number $n$, which will be the number of subsets we want to generate, the algorithm is as follows.

ret = {}
(While n > 0)
     T = SUBSET(S,k)
     ret.add(T)
     S = S / T
     n -= 1
return ret

In this snippet, I assume $S$ is the initial subset, $k$ is the desired sum, and $n$ is the number of subsets we want. Each time we calculate a subset, we calculate the set difference of $S$ and $T$ and set the resulting set equal to $S$, essentially removing the element of $T$ from $S$. Now, for the implementation of SUBSET, if you go with the dynamic programming approach, you can achieve a runtime of $O(xnk)$, where $n = |S|$. More info on the dynamic solution can be found here. https://en.wikipedia.org/wiki/Subset_sum_problem#Polynomial_time_approximate_algorithm. If you really want to optimize the runtime of SUBSET, the fastest algorithm I could find is outlined in this paper https://arxiv.org/abs/1507.02318, although it may not be practical to implement. If you're looking for a polynomial time algorithm, then I'm afraid you're out of luck since this problem reduces to SUBSET, which is an NP-Complete problem.


Why can't we mimic a dog's ability to smell COVID? As far as I can tell, we have invented tools and algorithm to:

Detect a wider range of colors at a larger range than humans or any other animals on the planet
Detect sound with wavelengths inaccessible to humans or most animals on the planet

But why is it that dogs can smell COVID or Cancer and we can't produce a similar tool to "smell diseases"? Why can't we mimic the dog's sense of smell: is it a hardware limitation or a software one? Am I mistaken in thinking that this sense is the hardest to mimic?

We can actually detect some diseases via smell, and the term to search for is olfaction.  The general problem is known as breath analysis.
However, the research into olfaction and machine learning is rather new (perhaps even surprisingly new).  As Lötsch et al. point out, little research (prior to the very recent research) on olfaction and machine learning has been performed, with a few exceptions:

Quantifying olfactory perception: mapping olfactory perception space by using multidimensional scaling and self-organizing maps, Mamlouk et al., Neurocomputing, 2003.
Relationships between molecular structure and perceived odor quality of ligands for a human olfactory receptor, Sanz et al., Chem Senses, 2008.
Diagnosis and Classification of 17 Diseases from 1404 Subjects via Pattern Analysis of Exhaled Molecules, Nakhleh et al., ACS Nano, 2017.
And the one mentioned above, Machine Learning in Human Olfactory Research, Lötsch et al, Chemical senses, 2019.

I don't know whether the problem in general is harder, but as you are touching  on in your question, the problem is much harder from a hardware perspective.  Where imaging only needs a simple camera, and hearing only need a simple microphone, to detect smell you need a so-called
as chromatography–mass spectrometry instrument. As the Wikipedia article mentions:

Breath gas analysis consists of the analysis of volatile organic compounds, for example in blood alcohol testing, and various analytical methods can be applied.

Here are some pointers from popular science that should assist you in getting into the literature:

Scientists Invent An AI That Can Smell 17 Diseases From Your Breath, Including Cancers

Innovative AI Breath Analyzer Diagnoses Diseases by “Smell”

AI is acquiring a sense of smell that can detect illnesses in human breath

Well, given this is a computing forum, I would say that all computing requires input. You have to have a way to "input" the smell. So far, as one of the answers described, we have very few ways of translating a smell which is a physical world thing, into data, and even so far, those methods mentioned have arguable limits on how they translate to a "smell".
Once that happens in a cost effective and available manner, everything else will just translate over, just like it did with imaging. As the old saying goes, Garbage in, Garbage Out. I'll add, Nothing in, Nothing out.


Algorithm for wait-for graph During the process of deadlock detection, the wait-for graph can be obtained from the resource-allocation graph. To detect whether there is a deadlock using the wait-for graph, can topological sort be used?

By making a slight modification, i.e., instead of removing the source as done in usual topological sort, we can remove the node (here, node represents a process) which does not point to another node first and proceed in this manner. As soon as the algorithm detects that it cannot proceed further and there are still nodes existing in the wait-for graph, it can be concluded as deadlock.

Other tags are topological-sort and deadlock-detection.

Hint: There is deadlock in the wait-for graph if the graph has directed cycles (why?). Perhaps topological sort is useful for detecting these.

IN single stance WFG the presence of cycle indicate that their is deadlock it is sufficient condition but in multi-instance WFG if the cycle is presence then we cant right away declare that their is deadlock it is just necessary condition not sufficient condition their might chance to presence. if the topological sorting is used then I think it always come up with the result that there is no deadlock just because topological order is acyclic graph and we know that deadlock to be present there should be presence of cycle .


Shortest path between all pairs with colored nodes I got a question from my homework in each I have the solution, but not the algorithm. I want to check if I understood it correctly.  The question is:

Let's say we have a directed graph with no cycles, it has N vertices and M edges.
Exactly 2018 vertices are colored green, and the others are black.
We know that in each shortest
path, each vertex is colored green,
perhaps without the first and the last node.

We can find the shortest path of all two pairs of nodes in:  O(___) and not less

What I tried:
If we run the Floyd Warshall algorithm on the 2018 green vertices we get the shortest path between all pairs of greens. (This is O(1) because of the green vertices amount is constant).

Now for each (u,v) in VxV:

If both u and v are green we already have the shortest path from Floyd Warshall.
If one is green and the other black, we add the edge's weight that connects the source/destination to the green group and add the Floyd Warshall result.
If both u and v, are black, we add the lightest weight of each which connects to the green group.

I think my solution is kind of messy, and I do not know if it's 100% correct.

The solution is: We can find the shortest path of all two pairs of nodes in:  O(n^2) and not less.

Your answer and reasoning are correct, but the last steps in your algorithm are wrong.

First, discard all edges with no green vertex.  Then:

To find the shortest path between a green and black node, you have to consider all of the black node's green-adjacent edges, and add the shortest path to/from the green.  There are at most 2018 of these, so it's still constant time.

To find the shortest path between two black nodes, you have to consider all combinations of their green-adjacent edges, and add the distance between the greens.  There are at most 20182 of these combinations, so it's still constant time.

So you can certainly do this in O(n2) time, and you can't do any better, because that's also the size of the output.

It may be simpler just to show how you can optimize Floyd-Warshall to take O(n2) time when all edges are known to be green-adjacent.

The time complexity of Floyd Warshall to find shortest path among all pairs of nodes isn't O(n^2). It's O(n^3).

  This is O(1) because of the green vertices amount is constant.

This is not correct. if the number of green node is G, then the complexity of running Floyd Warshall to find all pair shortest path among G nodes is - O(G^3).

Now the second part's complexity is correct. That's O(n^2) because you are traversing VxV nodes.

So your proposed solution would have a time complexity of - O(n^2 + G^3).

Now here what I don't know is - is N way more bigger than G(2018)? What you need to consider here - which one would take more computation? if n^2 is way bigger than G^3, then we can ignore the G^3 part as Big-O notation is the upper bound indication. And if G^3 is bigger then we can ignore the n^2 part.

Note - Now I am not sure about the not less part in your question. Big-O notation is the upper bound indication. This inherently mean that this solution would take X computation at most. You can see Big-O means not more. I think what your question expects is to find the lower bound(not less). If so, then it should have been Omega notation not Big-O.


Is the power of a regular language regular? Is the root of a regular language regular? If $A$ is a regular set, then:

$L_1=\{x\mid\exists n \geq0, \exists y \in A: y=x^n\}$,

$L_2=\{x\mid \exists n \geq0, \exists y\in A: x=y^n\}$.

Which one of them is regular?

My reasoning is since in $L_2$ we can have uncountable $x$ from even one value of $y\ (y^0, y^1, y^2,...),\ L_2$ cannot be regular. But that thinking seems wrong.

The language $L_2$ is not necessarily regular. Indeed, consider $A = a^*b$. If $L_2$ were regular, then so would the following language be:
$$L_2 \cap a^*ba^*b = \{ a^nba^nb : n \geq 0 \}.$$
However, this language is not regular (exercise).

In contrast, the language $L_1$ is regular. We can see this by constructing a DFA for it. Let the DFA for $L_1$ have states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$. The states of the new DFA are labeled by functions $Q \to Q$. The idea is that the new DFA is at state $f\colon Q \to Q$ if the original DFA moves from state $q \in Q$ to state $f(q)$ after reading $w$ (i.e., if $\delta(q,w) = f(q)$ for all $q \in Q$). The initial state is the identity function. When at state $f$ and reading $\sigma$, we move to the state $g$ given by $g(q) = \delta(f(q),\sigma)$. A state is accepting if $f^{(n)}(q_0) \in F$ for some $n \geq 0$.

I used the following reasoning, but it has a flaw, see comment below:

  $L_2$ is regular. As $A$ is regular, then there is a regular
  expression $e$ such that $A=L(e)$. It is easy to see that
  $L_2=L(e^*)$.