How does the token method of amortized analysis work in this example? Below is the description of the answer to a question which says the following:

Design a data structure to support two operations for a dynamic multiset S of integers which allows duplicate values.

Insert operation for one element
Delete-larger-half(S) deletes the
    largest ceil(|S|/2) elements from S.
m insert and delete-larger-half
        operations run in O(m) time.
Also output the elements in O(|S|)
            time.

In answer unsorted array has been taken. I think delete-larger-half corresponds to deleting the |S|/2 elements with highest magnitude. Then how does deleting with median work unless there is n comparisons (i.e compare each element with the median). I suppose the amortized analysis is what is bringing out the complexity. I'm looking for an answer that can explain the token based amortized analysis by using the example in this question.

What I know already: Amortized analysis means doing some expensive work in previous steps which leads to worst case of a following step not happening as often. Every time the expensive step occurs, the probability of it happening again reduces more and more. On average it evens out giving a better amortized complexity. Example: implementing dynamic array which is probably what has been done in the solution linked below.

Link to solution: https://courses.csail.mit.edu/6.046/fall01/handouts/ps7sol.pdf

  You use an unsorted array, so insert takes O(1) worst-case time. For DELETE-LARGER-HALF,
      you use the linear-time median algorithm to find the median, then you use PARTITION to partition
      the array around the median, then you delete the larger side of the partition in O(1) time.
      For the amortized analysis, insert each item with 2 tokens on it. When you perform a DELETE-LARGER-HALF
      operation, each item in the list pays 1 token for the operation. When you delete the larger half, the
      tokens on these items are redistributed on the remaining items. If each item on the list starts with
      2 tokens, they each have one after the median finding, and then each item in the deleted half gives
      its token to one of the remaining items. Thus, there are always two tokens per item and we get
      constant amortized time.

I've not been able to understand the logic behind random assigning of token and taking it off.

In the answer, the insert has been assigned 2 tokens, the find median and partition take away 1 token total. And then deletion gives the 1 token. I understand that each time, delete-larger-half is called, the next delete-larger-half's cost reduces drastically but why exactly the values 2, 1, 1 have been chosen?

Then how does deleting with median work unless there is n comparisons (i.e compare each element with the median).

After partitioning (they assume Quicksort-style partitioning), you can just delete the last $\lceil |S| / 2 \rceil$ elements in the array.

  Amortized analysis means doing some expensive work in previous steps which leads to worst case of a following step not happening as often. Every time the expensive step occurs, the probability of it happening again reduces more and more.

That is a useful intuition, but I feel a little bit besides the point.

Mainly, amortized analysis is about investigating the compound cost of sequences of operations. By dividing the sum by the number of operations we get what we call amortized cost for each operation.

I don't see a specification of such sequences in your problem statement so it may be ill-posed, unless the analysis goes through for all sequences.

So let us check. What is the worst that could happen? Well, probably a sequence of only DELETE-LARGER-HALF operations; consider $n$ elements and a sequence of $m = \lfloor \log_2 n \rfloor$ DELETE-LARGER-HALF operations (after this many, the set is almost empty). Since each operation has linear cost in the number of elements, the total cost then is $\Theta\bigl( \sum_{i=1}^{\log_2 m} 2^i \bigr) = \Theta(m)$ -- fits!

If we wanted to make this sequence more expensive by making individual summands larger, we would need to add INSERT operations. Say we wanted to increase one summand $2^i$ to $2^{i+1}$. We would have to add $2^i$ elements at cost $O(1)$ each, so the compound cost would increase by $2^{i+1}$ -- but $m$ would increase by $2^{i}$! Therefore, the amortized cost would only increase by a constant.

The core observation is this: if an element is to partake in making a DELETE-LARGER-HALF operation expensive (by being there), it has to be INSERTed first. Since DELETE-LARGER-HALF has linear cost, we can not add more than constant cost per element. In combination, this means we will get constant amortized time.

The tokens are a way to formalize this into a proof (which the part you quote does not quite manage to do). The way the tokens are set up and passed around, we see that the cost of any sequence of operations is in $\Theta$ of the total number of tokens we see. We can not possibly see more than $2m$ different tokens so we get an $O(m)$ bound on the compound cost or an $O(1)$ bound on the amortized cost.


Enumerable disjoint subsets whose union is equal to the union of the sets I'm given that two sets, $A$ and $B$ are enumerable. I have to show that there exist subsets $A \supset C$ and $B \supset D$ ($C$ and $D$ also enumerable) such that $C$ and $D$ are disjoint and $A\cup B = C \cup D$. I was thinking to take $A=B=\{0,1\}$ and define $C=\{n : f(n)=1\}$, $D=\{n: f(n)=0\}$.
Do you think this is right?

This answer assumes that enumerable means recursively enumerable.

Here is an enumerator for $C$:

Run enumerators for $A,B$ in parallel.
Whenever the enumerator for $A$ outputs a word, check whether the word has already been enumerated by the enumerator for $B$; if it hasn't, output it and continue.

The enumerator for $D$ is defined symmetrically.


How to do high performance string matching when comparing unordered sets of tokens This is the problem:

I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one time in a string).

I want to know if a new string matches any of them without taking token order into account.

The metric I think about is something like this (comparing two strings at the time, this is the first thing that came to my mind when trying to solve the problem and don't know if it is already used), a matching percentage calculated like this:

Match_Metric(A, B) = number_of_matched_tokens(A, B) / max_number_of_tokens_in_any_of_two_strings(A,B) * 100.

Example:

String 1: "abc, cde, ghi, adc, dca, aab"

String 2: "cd, r, a, x"
String 3: "aab, cde, ghi, abc, adc, dca"
String 4: "aab, cde, ghi, abc, adc, dca, rrrm, a"

1 vs 2 = 0%
1 vs 3 = 100%
1 vs 4 = 75%

What I am trying to avoid is to perform a one to one comparison between tokens, but I am finding that other techniques like edit distance won't give me an exact match in the case of 1 vs 3 unless I first order the tokens.

The problem can be extended to do a string search within the tokens, for example:

String 1: "abc, cde, ghi, adc, dca, aab"

String 2: "cd, r, a, x"

As "d" appears in one token in 2 and three tokens in 1, that can affect the metric. In this case an approximate string matching technique such as "edit distance" would be useful but in a token versus token approach. The formula would be more complicated in this case, instead of having an integer representing the number of matched tokens it would be a fraction number and could be calculated like this:

Comparing two tokens at the time one from the string A and one from the string B:

token_match(a,b) = 1 - edit_distance(a,b) / length_of_largest_token(a,b)

So the general metric would be:

String A = {a0, ..., an}
String B = {b0, ..., bm}

i = {0, ..., n}
j = {0, ..., m}

Match_Metric(A, B) = sum(token_match(ai, bj)) / max_number_of_tokens_in_any_of_two_strings(A,B) * 100

Any ideas on what technique/algorithm is more broadly adopted/used for this problem?

So you want to use the Jaccard index as your metric of similarity.  Well, the Wikipedia page for the Jaccard index (and which I linked to in the comments above) already has some hints on methods for finding close matches, more efficiently than comparing all pairs.  For instance, you can use locality-sensitive hashing.  Hint for the future: you might want to do more research in the future based on feedback from folks, as locality-sensitive hashing was already suggested in the comments and a relevant Wikipedia page was also mentioned in the comments.

If tokens are not too common, there's another alternative method you could also try.  You could build an inverted index: an index that, for each token, lists all of the strings that contain it.  Now given a new string S, it's easy to enumerate over all of the tokens in it, look each one up in the inverted index, find all other strings that share at least one token in common with S, compute the similarity between that string and S, and keep the best one.  As long as no string contains too many tokens and no token is present in too large a fraction of strings, this will perform better than all-pairs comparison.

Your "extended" problem is different in nature and would probably be better asked as a separate question.  It might be a much harder problem.


Matrix of Matrices in Python I want to create a matrix where each entry itself is a random matrix.
What would be a good way to represent this?

It is not necessary but some hints on how to implement your proposed solution in Python would be useful.

What you are looking for is just a higher dimensional array.

Let's say you want a 5x5 array where each element is a 2x2 array with random number. You can easily represent that as a 5x5x2x2 array.

If you are happy about using numpy

A = numpy.random.rand(5,5,2,2)

Will create a 5x5x2x2 array.

You can use the first two indexes to access your 2D random arrays.

print A[1,1]

Results in:

[[ 0.68527006  0.37304491]
 [ 0.23281899  0.46951261]]


Is it correct to use the pinhole camera model to get the mapping of a 3D line to a line in an image? I've been working on a computer vision project in which I'm using the pinhole camera model to map one line of the world to one line in an image.

From previous research on the topic, I know that it is possible to map a point in the 3D world to a point in one image using the projection matrix obtained by calibrating the camera you're using to get the images of the 3D world. This mapping can be done as follows:

$ \lambda \begin{bmatrix}u \\ v \\ 1\end{bmatrix} = P \begin{bmatrix}X \\ Y \\ Z \\ 1\end{bmatrix}$,

in which $(u,v,1)$ are the coordinates of the point in the image, $(X,Y,Z,1)$ are the coordinates of the same point in the world and $P$ is the projection matrix.

A line in the image can be defined as:

$\begin{bmatrix}A & B & C\end{bmatrix}\begin{bmatrix}u \\ v \\ 1\end{bmatrix}$,

in which $(A,B,C)$ are the parameters used to describe the line. My research also taught me that perspective projections preserve lines, i.e., a straight line in the world will map to a straight line in the image.

Using the description of a line and the method used to get the mapping of points, I got this model:

$ \lambda \begin{bmatrix}A & B & C\end{bmatrix} \begin{bmatrix}u \\ v \\ 1\end{bmatrix} = \begin{bmatrix}A & B & C\end{bmatrix} P \begin{bmatrix}X \\ Y \\ Z \\ 1\end{bmatrix}$.

I've done some additional research, but so far I haven't found anything that can support this affirmation.

Is it correct to say that the mapping of a 3D line in the world to a line in an image of the world is done using the previous model?

Could anyone please point me in the right direction?

Thank you.

The assumption is correct, if(f) you project the 3d line into the rectified image. The idea of projecting a 3d-line to a pixel-line is most often used in a stereo setup with two cameras: if the left camera sees a features at a certain pixel, then you know that this object is on a 3d-ray that corresponds to this pixel. If you want to search this object in the right camera's image, you only have to search on the pixel line that corresponds to this 3d-line.
Keywords are here epipolar geometry or epipolar line:
https://www.robots.ox.ac.uk/~vgg/hzbook/hzbook1/HZepipolar.pdf


Solving the recurrence $ T(n) = \dfrac{T(n-1) + T(n-3)} {T(n-2)} $ What's the (asymptotic) solution of the following recurrence?
$$ T(n) = \frac{T(n-1) + T(n-3)} {T(n-2)}. $$
I tried to solve this with generating functions to find an accurate bound.

The solution depends on the initial conditions. For example, if $T(0) = T(1) = T(2) = 2$ then $T(n) = 2$ for all $n$, but in general the recurrence converges to a pattern of length $4$. The limiting patterns are of the form
$$
a, \frac{ab\pm\sqrt{(ab)^2-4(a+b)}}{2}, b, \frac{ab\mp\sqrt{(ab)^2-4(a+b)}}{2}
$$
For example, if $T(0)=T(1)=T(2)=1$ then $a ≈ 3.13200592382654$ and $b ≈ 1.35282312408545$. For large $n$, the values $T(4n),T(4n+1),T(4n+2),T(4n+3)$ are close to
$$ 3.13200592382654, 2.06091243965066, 1.35282312408545, 2.17613759887451. $$
(So we choose $-$ in the $\pm$.)
The above was determined empirically. It would be nice to come up with a proof.


We say that a function $f$ is $O(g)$ if there exist constants $M$ and $C > 0$ such that
$$
 x > M \Longrightarrow f(x) \leq C g(x).
$$

It shouldn't be too difficult to show that $x^3$ is $O(x^4)$ using the definition.

To show that $f$ is not $O(g)$ you need to show that for every $M$ and $C > 0$ there exists $x > M$ such that $f(x) > C g(x)$. While using this to refute "$x^4$ is $O(x^3)$" is a bit awkward, I think that it's a good exercise which is not too difficult.

Later on you might learn other ways of showing that $f$ is not $O(g)$. Very briefly, the idea of the other methods is a two-pronged attack:

If $f$ is $O(g)$ then X.
X is false.
Therefore $f$ is not $O(g)$.

I'll let your professor give you examples of X.


interference graph: assigning variable to itself I'm studying the theory behind compiler design, and was assigned with building an Interference graph for a certain code 3-address code.
We were taught to first divide the code into blocks (according to GOTOs), and draw lines that represent a variables lifeline.
I am not sure on a = a op c (that is, same variable is both read and assigned in same command).
I am following this examples, which sadly, has a typo that makes it hard to understand this very end-case. Here, a=a+b+c, so a is both used and assigned.
I have initially treated that with no special care (logic being "i know some interpreters can read RHS before LHS"), but now I am not quite sure. My question really:I think perhaps the example should have mark a's line starting from the read() command, end it in the a=a+b+c but also re-draw the line. This way an extra register will temporarily hold a's value before assigning it back to a. Is that correct?

You are right. The lifetime of a could be split into two spans. That said, how would you notate that in the interference graph? That is, how would you notate that one variable only interfered with one span of another variable's lifetime?

This is one of the motivations for Static Single Assignment (SSA) form. By having each assignment write to a "new" variable, you're never in the situation where a variable's lifetime is in potentially disjoint spans. You also have a name for each span of a (source-level) variable's lifetime, so the interference graph can be finer grained.

It is, however, safe to treat the lifetimes as starting at the first assignments and ending at the last uses. So while it may not be optimal to give each variable one single span of lifetime, it will never cause incorrect behavior.


Semantic natural language processing - from texts to logical expressions? Universal knowledge base? My question is - is there a semantic natural language processing that tries to understand the meaning of the texts and that tries to derive the consequences of the understood meaning? Is there a universal knowledge base that can be used for the "grounding" of the texts?

I have heard a lot about statistical NLP and NLP with neural networks but those approaches are not scalable, are not exact and are not satisfying. Is there (and if not - then why) a semantic NLP and semantic natural language understanding that tries to translate the texts into logical formulas? Today we have a vast array of logical formals - both rigorous and both nonmontonic, adaptable, fuzzy, probabilistic and so on? So - if we have those logics why don't we translate texts into them?

And if texts are translated into logical formulas then the universal knowledge base (KB) can be built. This KB should be used as reference KB. I.e. if some text contains the phrase "logical continuum" then this KB should contain all the possible definitions (expressed as logical formulas) of this phrase (according to the different texts, authors) and one should be able to reason over those definitions, to use definitions for applying this phrase into the new text (possibly - computer generated texts), to use definitions for deriving more general or more special notions with relevant definitions, to form completely new concepts. There can be two types of terms in this KB: abstract ideas and concrete real world facts, like country Belgium and so on.

I am aware of existence of some KBs like ConceptNet and WordNet (not really useful) and Cyc/OpenCyc (formal KB with reasoning capabilities) and there is also very promising framework OpenCog which (fortunately) has interesting reasoning engine, but (unfortunately) lacks the public knowledge base for experiments. OpenCog is really interesting, because it unifies probabilitist and rigorous reasoning: each concept (Atom in their terms) have strength/probability value and if those values converge to 1, then proababilistic reasoning tends to rigorous classical logic style reasoning. But that's all.

So - are there such notion as semantic NLP and are there endeavours to create universal knowledge base for semantic interpretation of any text? Are there ongoing projects in this field?

There are several implementations of semantic parsers that convert natural-language texts into formal logical representations of their meanings. Natural language understanding systems can also be based on discourse representation theories that represent the meanings of English texts using first-order logical predicates.

I have found at least one system that is able to generate a knowlege base from statements that are given in a natural language. The ACE Wiki is based on Attempto Controlled English, which is a semantically unambiguous subset of the English language.


P-NP related 3 sub-problems This is a question on a practice final.

Which of the following statements are true? If it is false, what is the underlying reason behind that?

I. If 3-CNF-SAT is in P, then Clique is also in P.

II. For decision problems $L_{1}, L_{2}$ in NP, if P is not NP, $L_{1}$ is at least as hard as $L_{2}$, and $L_{2}$ is at least as hard as $L_{1}$, then $L_{1}$ and $L_{2}$ are NP-complete.

III. For decision problems $L_{1}, L_{2}$ in NP-complete, if $L_{1}$ is not in P, then $L_{2}$ is also not in P

We are told that only the third statement is True, but there's no explanation why on the key. I have tried to figure this out, and the only conclusion I've come to is:
(I) cannot be true because if A is polynomially reducible to B, this implies B is at least as hard as A, not vice-versa (Not sure if this is a correct conclusion, so feedback on this would be appreciated.)

This is the first time I'm learning about the notion of hardness, so I don't understand most of the technical explanations I've found. Any clarifications on why I, II is incorrect, and why III is correct would be appreciated.
Self study I've done includes reading multiple StackExchange posts, multiple Wiki pages, and the corresponding section in the Cormen book. I just personally understand concepts better if I see different explanations.

You are right about $1$.
For $2$, $L_1$ reduces to $L_2$, means $L_1$ as least as hard as $L_2$. But not vice versa as adding numbers is in $P$ and tower of Hanoi is in $EXP$, so the later is hard but addition does not reduce to tower of Hanoi. Just knowing the hardness does not say much. Hence the statement is false. If it were not the case, then statement $2$ would have been true.
For $L_1, L_2\in NP\;Complete$, as $L_1,L_2\in NP$, $L_1$ reduces to $L_2$ and $L_2$ reduces to $L_1$, according to NP-Complete definition. So, their hardness is same. So, they both belong to the same class. Hence, $L_1\in P\Rightarrow L_2\in P$ and vice versa. So, $3$ is correct.


Is there a difference between pure binary and binary? In some books and on the internet I occasionally find "pure binary" and "binary" on its own, is there a difference between these two terms? If so, can someone describe briefly what they are?

I'm guessing here for lack of context, but I think the following distinction is reasonable.

A binary encoding is anything that maps stuff to bit strings. There are many, including two's complement, IEEE float, ASCII, and so on.

Pure binary probably refers to bland natural numbers written in base two, i.e.
if $n_{(2)} = a_k\dots a_0$ then

$\qquad\displaystyle n = \sum_{i=0}^{k} 2^ia_i$.


A problem about asymptotic functions Are there two function $f:N\rightarrow N$, and   $g:N\rightarrow N$ such that $f(n)+g(n)\ne O(f(n))$ $\wedge$ $f(n)+g(n)\ne O(g(n))$?
My idea:  i think because of for any $f:N\rightarrow N$, and   $g:N\rightarrow N$ then $f(n)+g(n)= O(\max \{f(n),g(n)\})$ then there are no two such functions.
is my argument is valid?

Let $f(n) = \begin{cases}
1 & \mbox{if $n$ is odd}\\
n & \mbox{if $n$ even}
\end{cases}$, and $g(n) = \begin{cases}
n & \mbox{if $n$ is odd}\\
1 & \mbox{if $n$ even}
\end{cases}$.
Then, $h(n)=f(n)+g(n) = n+1 \not\in O(f(n))$.
Indeed, for any $n_0$ and $c>0$, there is some $n \ge n_0$ such that $h(n) > c f(n)$.
Simply pick $n$ as an odd integer greater than $\max\{c, n_0\}$, e.g., $n=2\max\{c, n_0\}+1$. Then $h(n) = n+1 = 2\max\{c, n_0\} + 2 > c = c \cdot 1 = c f(n)$.
A similar argument shows that $h(n) \not\in O(g(n))$.


Prove or disprove the bound given the recurrence relation Given the following recurrence relation,

$T(n) = 2 T(\frac{n}{2}) + f(n)$,

where $f(n) = \Omega(n^2)$, I'm asked to prove or disprove that $T(n) = O(f(n))$.

If I'm allowed to restrict my discussion within the special cases in which that $n = 2^k$ for positive integer $k$, how can I prove or disprove the proposed bound, $T(n) = O(f(n))$?

As a side information, if $f(n) = \Theta(n^2)$, then we can show that $T(n) = \Theta(f(n))$ by the Master Theorem. But how should I handle the subtlety of this case with big-Omega and big-O?

Thanks for the help.

Your recurrence relation is covered by case 3 of the master theorem:

  If

  $T(n)=aT(\frac{n}{b})+f(n)$ where $a\geq 1$ and $b>1$
  $f(n)\in\Omega(n^c)$ where $c>\log_b a$
  $af(\frac{n}{b}) \leq k f(n)$ for some constant $k<1$ and sufficiently large $n$

  then $T(n)\in \Theta(f(n))$

Note that $T(n)\in \Theta(f(n))$ means that both $T(n)\in O(f(n))$ and $f(n)\in O(T(n))$. So $T(n)\in O(f(n))$ follows from $T(n)\in \Theta(f(n))$.

In your case, you have $a=b=2$ and $f(n)\in\Omega(n^2)$ where $2 >\log_2 2 = 1$. The only problem is that you cannot guarantee $2f(\frac{n}{2})\leq kf(n)$ for some constant $k<1$ and sufficiently large $n$.

So you can disprove $T(n)=O(f(n))$ by a counterexample like $f(n)=n^2+\exp(n)\cos^2(\frac{\pi}{2}\log_2 n)$. Not really a great example for a nice exercise, but OK.


Broadcast with Limited Spreading Let consider well-known problem in distributed computing Broadcast Problem in network with stopping crashes.

The most appropriate solution to the broadcast problem is flooding algorithm, when the source of the message just send it to all available nodes of the network on the first round, if there are crashes on the edges some number of message will fail. Then on the second round, the nodes that received messages from the previous round send it to all available nodes and so on.

Let consider slightly different model, when on  every round the source node with message is capable to send a message to only one single node of course stopping failure might occur. It's very useful model, which can represent a sort of controllable or limited spreading.

Unfortunately I don't know the formal name of the model. Do you familiar with result in the model of "limited spreading", I am sure there are must some work in this direction.

Canonical solutions to the broadcast problem include, as you mention, flooding (controlled & uncontrolled, although uncontrolled flooding is untenable for a variety of reasons), as well as spanning-tree based approaches and N-way unicast (which is basically just to point out that broadcast protocols don't represent fundamentally more powerful communication mechanisms).

What you're asking about sounds somewhat similar to a sort of controlled flooding with fault tolerance. Alternatively, you might conceive of your scheme as a spanning-tree approach where multiple redundant spanning trees are defined for each node. In fact, a hybrid of these approaches would help avoid loops, explosion, etc.

Kurose and Ross provide a good explanation in their book "Computer Networks - A Top Down Approach", which you might use to develop your own broadcast protocol.


A question about linked list I would like to check the answer of this exercise:

A circular doubled linked list with N elements has pointers that cost k bytes each of space in memory. How many bytes do the pointers of this list cost in total?

Researching about circular linked lists, i can assume that each node has 2 pointers. So am i right to say that the answer is 2(n)k bytes?

Thanks.

The list takes $2*N*k$ bytes in total. A circular linked list is just a simple linked list with its last node's next pointer pointing back towards head. So, no extra pointer is required to make it circular. Hence, the total space is $2*N*k$.


Complexity of simulating idle games (pt1) An idle game (Cookie Clicker is a well-known example) is a game where you set up automatic resource production, and most of reasonable human play is then waiting as resources accumulate. Typical implementation is in the form of a "tick loop", where resources update say once per second, generally increasing.
But many games can implement an "offline mode" where instead you can exactly calculate any number of ticks in one step. For example if you were producing 1000 cookies/second, and you come back after 1 hour, you've produced 3.6 million cookies exactly--no need to simulate all 3600 ticks. Then the player can reduce the update rate on screen, or come back to the game in 5 hours without running a program continuously. (Aside: many real games offer an "offline mode" which does NOT exactly match what would happen playing the game for the same length of time, but here I'm asking about exact simulation).
I am trying to figure out for which idle games an it's possible to efficiently compute many ticks in one step ("offline mode").
In a typical idle game (think "cookie clicker"), you have a bunch of resource generators, and each one generates some resources each tick. For example, maybe you have a cookie stove, which produces 5 cookies/tick. And you could also have a generator factory, which produces 1 cookie stove/tick.

For each resource, it produces some fixed list of resources each tick. Let's say we just have a list of what each resource produces each tick.

A resource costs something to buy. This is actually irrelevant for the simulation--buying is only a player action, and can't be done automatically.

A problem input will be a set of starting resources, and a number of ticks to simulate. Output should be the resources after that number of ticks.

If there are no cycles, an offline mode is definitely possible. The number of each resource is a linear (if it is not produced by anything else), quadratic (if it is produced by a linear resource), etc. So it's always a polynomial, which is easy to calculate.

My first question: is this still easy if we allow cycles, ex a "general purpose factory" that produces both general purpose factories, and cookies?
Second question: is this easy if we allow simple "autobuy"? Ex. convert 1000 cookies into a cookie factory, and buy as many as possible, on each game tick.
If it's easy, show how to do it. If it's hard, prove it!

As you have said in your question, non-cyclical resource production is easy to simulate, but let's describe the simple case before seeing how it impacts the answer. For our cookie-bakery scenario, this is the setup:
$$
t_i=0,\ t_f=100 \\
C_i=567,\ C_{cpt}=0,\ C_{bpt}=0 \\
B_i=10,\ B_{cpt}=2,\ B_{bpt}=0
$$
The above describes the initial state of our game, we currently have 567 cookies and 10 bakeries. It also describes the production statistics, how much each resource produces per tick. For us, cookies produce nothing and bakeries produce 2 cookies per tick. How do we find how many cookies there are when the time is up?
$$
C(t_f)=\int_{t_i}^{t_f}\frac{dC}{dt}dt+C_i=2567
$$
This function will calculate how many cookies have been produced by time $t_f$. In our simple case, $\frac{dC}{dt}$ is easy to calculate:
$$
\frac{dC}{dt}=B_{cpt}B(t)=20
$$
Since there are no new bakeries being generated, the number of bakeries is constant $B(t)=B_i$.

Question 1
The trouble begins when the resource production contains cycles. That is to say, $\frac{dC}{dt}$ is dependent on $C(t)$ itself. We have entered the realm of differental equations. For an example, here is a tweaked setup where cookies can also asexually reproduce every tick:
$$
t_i=0,\ t_f=100 \\
C_i=567,\ C_{cpt}=1,\ C_{bpt}=0 \\
B_i=10,\ B_{cpt}=2,\ B_{bpt}=0
$$
Now the rate of change for cookies looks like:
$$
\frac{dC}{dt}=B_{cpt}B(t)+C_{cpt}C(t)\text{ where }C(0)=C_i
$$
For our case, this is a linear first-order differential equation, our integrating factor is:
$$
\mu(t)=e^{-C_{cpt}t}
$$
Plug it into the differential equation form:
$$
C(t)=\frac{B_{cpt}B(t)}{-C_{cpt}}+ce^{C_{cpt}t}
$$
Find our constant $c$ by checking the initial condition:
$$
C(0)=\frac{B_{cpt}B(0)}{-C_{cpt}}+ce^0=C_i \\
c=C_i+\frac{B_{cpt}B_i}{C_{cpt}}
$$
Plug it back into our original equation:
$$
C(t_f)=\frac{B_{cpt}B(t_f)}{-C_{cpt}}+\bigg(C_i+\frac{B_{cpt}B_i}{C_{cpt}}\bigg)e^{C_{cpt}t_f} \approx 1.58\times 10^{46}
$$
The asexual reproduction of cookies produces substantially more cookies than just bakeries, but keep in mind the cookie population is essentially doubling every time plus new cookies are being produced by bakeries.
This method can be extended for larger cycles instead of just self cyclical, but it requires higher order differential equations.
Note: Since we are just evaluating an exponential function, it is extraordinarily efficient, $O(1)$. However, this solution adapts the mathematics of population growth estimates to fit this discrete system and will only produce an approximation. Depending on how many timesteps are required to simulate, it may be preferable to spend more time computing an exact result.

Question 2
Automatic buying is quite a bit more difficult to achieve because the functions showing resource counts are no longer smooth and continuous.

This graph shows the cookie production assuming starting with one bakery & zero cookies and buying another bakery every thousand cookies. The period of the function decreases with time because more and more bakeries are added to produce cookies. An estimation could be created by fitting a function to the period, but I do not know of a method to exactly count the number of bakeries and cookies without checking each timestep.


Show that problem of Shortest-Path in digraph is in NL Look at solution to exercise 2, please.
Exercise and solution is derieved from:
https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/sol8.pdf

  $$ShortestPath = \{(G, k, s, t)| \text{the shortest path from $s$ to
> $t$ in $G$ has length $k$}\}$$ (a) Prove that $ShortestPath$ is in
  $NL$.

  (a) Solution:   We construct a $NL$-machine for ShortestPath as
  follows: on input $\langle G, k, s, t\rangle$, first compute $r_{k−1}$
  (the number of vertices reachable from $s$ in at most $k − 1$ steps).
  Then, on input $\langle G = (V, E), k, s, t\rangle$ and $r_{k−1}$ on
  the work tape,

d ← 0
flag ← FALSE
for all w ∈ V do
p ← s
for i ← 1 to k − 1 do
non-deterministically pick a neighbor q of p
if p = w then
d ← d + 1
if w = t reject
if w is a neighbor of t then
flag ← TRUE
if d < r_{k−1} reject
if flag then accept else reject

I don't know why it is so complex.
Tell me please, why direct and simple algorithm is not ok:
Check if there exists path from $s$ to $t$ of length $1$
Check if there exists path from $s$ to $t$ of length $2$
...
Check if there exists path from $s$ to $t$ of length $k-1$
If there exists path of length $\le k -1 $ then reject. Else check if exists length of $k$ and accept if exists.

In other words we check one be one each length. We can check existence of path thanks to non-determinism. We launch number of visited nodes and check if we end up in $t$

The difficulty here is how to check using non-deterministic logarithmic space that there is no path from $s$ to $t$ of some length $\ell$. We cannot just go over all possible paths of length $\ell$ since in order to do this we will need to "remember" $\ell$ vertices, whereas we are only allowed to remember $O(1)$ vertices (since each vertex takes up $\Theta(\log n)$ space).

If we want to check that there exists a path of length $\ell$, we can simply guess the path vertex-by-vertex and check that it leads from $s$ to $t$; this only requires counting up to $\ell$, which takes logarithmic space (since we're only interested in $\ell < n$). But it's not so clear how to check that there doesn't exist a path of length $\ell$ – what would be a witness for that?

The solution is to use the technique of inductive counting, invented for the proof of the Immerman–Szelepcsényi theorem, which states that NL=coNL. This is what the solution uses.


Selecting vertices in a graph in an order to keep border vertices as few as possible I am given an undirected graph. Initially all vertices are white. I need to color them black in such an order that the maximum number of vertices which are on the border between black and white regions is minimal. Is there an algorithm to find an optimal order for that?

More formally. We are given an undirected, connected graph $G = (V,E)$ consisting of $n$ vertices. I am looking for a sequence of increasing subsets of vertices $V_0, V_1, ..., V_n$, where
$V_0 = \emptyset$, $V_{i+1} = V_i \cup \{v\}$ for some $v\in V$, and $V_n = V$.
For any subset $W \subset V$ we define a cost function $c(W)$ as the number of "border" vertices, i.e. size of $\{w\in W : \exists m\in V\setminus W: (w,m)\in E \}$. I am looking for such a sequence where $\max_i(c(V_i))$ is minimal.

I feel my problem is somehow related to maximum flow algorithms, the same way as minimum-cut problem is. I think there must be a name for this (or similar) problem. However, as I was mixing "minimal cut" in various ways in the search engines, I was unable to find it.

A bit of context: I have a series of tasks to perform (edges), each loading two files from a disk (vertices). In order to speed up the process, I don't want the reload every pair of files every time. Instead, I want to keep some files in memory so that I can reuse them when another task uses the same file. But I cannot keep all files that there are because of memory constriants. The above sequence would help me select an optimal processing order, keeping the number of active files to minimum.

At first I didn't see how the problem underlying your actual application of using file buffers optimally matched your formulation. But as you mentioned in a comment, they are in fact two equivalent ways of describing the same problem, which amounts to generating a valid maximum-buffer-size-minimising sequence of operations, with each operation being one of "Load file $x$ to a free buffer slot", "Discard buffered file $y$ from its buffer slot" or "Process edge $(u, v)$" with $u$ and $v$ both being currently-buffered files:

Order vertices (your sequence of larger-by-one sets is equivalent to a vertex ordering) so as to minimise the maximum number of "border" vertices, which correspond to files already loaded into the buffer and which cannot be discarded yet because they are still needed in the future. A sequence of operations can be generated from this vertex order as follows: After choosing a vertex to blacken, load it to a free slot and immediately process all edges it has to existing black vertices (which we know by induction to be still in the buffer) in some arbitrary order, and then (again in arbitrary order) discard from the buffer any of them that have no more white neighbours.
Order edges so as to minimise the maximum number of "live" vertices, where a vertex becomes live the first time an edge it is incident on appears, and ceases to be live just after the last such edge. A sequence of operations can be generated from this edge order as follows: Load any vertices necessary for the current edge (in either order if neither is in the buffer yet), process the edge, discard from the buffer any vertex that is no longer live (again in arbitrary order).

I see now that your "border" is the same as my "live".

It's NP-hard

Fewest buffer slots needed to avoid reloading

If you want to know the smallest number of buffer slots required to process every file-pair (edge) without ever reloading a file (vertex), this problem is equivalent to the Vertex separation number problem, in which the goal is to choose, from all possible vertex orderings, an ordering that minimises the maximum number of "live" vertices, where a vertex is live at time $i$ iff it appeared before position $i$ in the sequence and has an edge to any vertex at position $\ge i$ in the sequence. Basically, a live vertex at some point in time is a file that has been loaded already but can't be discarded from the buffer yet because it is needed again in the future.

The vertex separation number is another name for the pathwidth of a graph, which is known to be NP-hard to compute. (And finding an actual solution -- a sequence of loads that meets this bound -- is at least as hard as this, of course.) No one knows how to solve an NP-hard problem exactly in subexponential time w.r.t. its size, so any algorithm to solve this problem will be likely be very slow for $n > 20$ vertices or so. The only bright side here is that you don't have to feel bad about using a brute-force solution, like trying all possible vertex orderings. Some tricks may give good speedups in practice, like branch and bound (noticing when your sequence of vertices so far is already worse than a complete solution found earlier, and halting recursion early).

Fewest loads needed for given buffer size

If you have a fixed number $b$ of buffer slots and want to know the smallest number of loads that would be needed using that many slots, this problem is at least as hard as the former one: Any algorithm that answers this question can easily be changed to answer the former one, by binary-searching on $b$ until you find that the answer is equal to the number of vertices (files), $n$. (Again, finding a sequence of loads meeting this bound is at least as hard as this.)

Heuristics

The above explains why you can't expect to solve large instances of this problem quickly and optimally. If you don't care too much about optimality, many heuristics are possible.

Probably the simplest, and what I would try first, is just trying many different random orders, measuring each, and returning the best. Alternatively, start from a random order and look for local improvements, like swapping each pair of vertices, and greedily take the new solution if it is better. When no better solution can be found, restart with a fresh random order. Repeat this as many times as you feel like.

Alternatively you could repeatedly choose a vertex of minimum degree, and process all edges incident on it that have not already been processed. A minimum-degree vertex can be chosen in constant amortised time, and this approach bounds the number of loads by $kn$, where $k$ is the degeneracy of the input graph -- a number that is likely to be low on sparse graphs. Often there are multiple elimination orderings, which may require different numbers of reloads, so this basic strategy could probably be improved quite a bit by tracking which vertices currently have all their neighbours already in the buffer, immediately processing all edges incident on them, and then discarding them.


Lower Bound of Matrix Multiplication I am reading the textbook algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

The authors state in page $67$:

  The preceding formula implies an $O(n^3)$ algorithm for matrix multiplication: there are $n^2$ entries to be computed, and each takes $O(n)$ time. For quite a while, this was widely believed to be the best running time possible, and it was even proved that in certain models of computation no algorithm could do better. It was therefore a source of great excitement when in $1969$, the German mathematician Volker Strassen announced a significantly more efficient
  algorithm, based upon divide-and-conquer.

The statement that interests my more in this quotation, is:

  it was even proved that in certain models of computation no algorithm could do better.

Could anyone support me with some references where I can find a proof of that kind?

Strassen, in his paper describing Strassen's algorithm (Gaussian elimination is not optimal) mentions

  the result of Klyuyev and Kokovkin-Shcherbak [1] that Gaussian elimination for solving a system of linear equations is optimal if one restricts oneself to operations upon rows and columns as a whole.

The reference is to

  Klyuyev, V. V., and N. I. Kokovkin-Shcherbak: On the minimizations of the number of arithmetic operations for the solution of linear algebraic systems of equations. Translation by G. I. Tee: Technical Report CS 24, June 14, 1965, Computer Science Dept., Stanford University.

The paper is available online.

In modern literature this result is virtually unknown, and I am not aware of any other lower bound on matrix multiplication beyond the $\Omega(n^2)$ lower bounds of Bshouty and Shpilka and the $\Omega(n^2\log n)$ lower bound of Raz.


Object recognition - given an image, does it contain a particular 3D object of interest? I have in mind a particular 3D object.  Given an image taken by a camera, I want to check whether that image contains an instance of my object.

For instance, let's say that the object is a bathroom sink.  There are many kinds of bathroom sinks, but they tend to share some common elements (e.g., shape, size, color, function).  There can also be significant variation in lighting and pose.  Given an image, I want to know whether the image contains a bathroom sink.

How do I do that?  What technique/algorithm would be appropriate?  Is there research on this topic?

Of course, it is easy to use Google Images to obtain many example images that are known to contain a bathroom sink (or whatever the object I'm looking for might be), which could be used for training some sort of machine learning algorithm.  This suggests to me that maybe some combination of computer vision plus machine learning might be a promising approach, but I'm not sure exactly what the specifics might look like.

If you have one or several images of a particular "sink" or object, then you can possibly use SIFT or SURF or other feature extraction/matching algorithms to match the objects up. You can investigate the OpenCV project (wikipedia, project); it includes many of these (possibly patented) algorithms. You can get an idea of how they work and what they can do by searching youtube for "opencv". If you specialize in matching previously known instances of a particular object, this might be appropriate. Additionally, there is much research specializing in facial recognition, so you can possibly find work on that.

Another project of interest: Sketch2Photo: Internet Image Montage. I don't know how they do it though, or if it can reliably identify anything; it seems to rely on some sort of recognition, and semantics search as well (you must name the objects in the sketch). You can read their paper (PDF)

If you want to recognize a generic "sink" concept or many multiple generic concepts, then it is bordering on strong(er) AI. There are lots of machine learning projects, and I am not sure which are useful for this or practical, but to demonstrate how cutting edge this is (and possibly not practical unless you spend a lot of time and research), Google (paper (PDF)) has made a giant GPU neural network that it successfully trained to recognize cats, presumably learning some sort of ability to conceptualize a more abstract "idea" of what a cat looks like. Related work by Yoshua Bengio; wired article; open source project.

This is "cutting edge", so again not practical, but just pointing out that you are trying to recognize generic things, and Google is working so hard just to recognize generic cats, you are in for a lot of work, or a restriction/trick/shortcut.


Finding the smallest number that scales a set of irrational numbers to integers Say we have a set $S$ of $n$ irrational numbers $\left\{a_1, ..., a_n\right\}$.

Are there any known algorithms that can determine a scaling factor $s \in \mathcal{R}$ such that $s * a_i \in \mathcal{N} \;\forall a_i \in S$, assuming that such factor exists? If multiple exist, how about the smallest one?

Moreover, I wonder, under what input conditions could one assume that an algorithm for this problem can't (or can) return a valid scaling factor?

I'm assuming that $0 \not \in \mathbb{N}$, otherwise $s=0$ is a trivial solution.

If you input numbers contain at least one positive and one negative number there is no solution.
If your input numbers are all negative, either there is a solution but no smallest solution, or there is no solution at all. You can decide which of the two is the case by solving the same problem on with the numbers multiplied by $-1$.

Assume then that all input numbers are positive.

If $s a_1 = c$ and $s a_2 = c'$ for $c,c' \in \mathbb{N}$, then $c' = s a_2 = c \frac{a_2}{a_1}$, i.e., $\frac{a_2}{a_1}= \frac{c'}{c}$. This shows that you can only find a solution if all your irrational numbers can be obtained by multiplying $a_1$ by some rational factor.

In this case you can consider the set of numbers $\{1, \frac{a_2}{a_1}, \frac{a_3}{a_1}, \dots, \frac{a_n}{a_1}\}$ instead. Since they are all rationals you can write them as $\{1, \frac{b_2}{c_2}, \frac{b_3}{c_3}, \dots, \frac{b_n}{c_n}\}$, where $b_i,c_i \in \mathbb{N}$ and $gcd(b_i,c_i)=1$. You can then find the minimum common multiple of the denominators and multiply it by $a_1^{-1}$.


Finding a source of a directed acyclic graph in linear time Given a directed acyclic graph $D = (V,A)$, a vertex $v \in V$ is a source if its indegree is zero, meaning that it has only outgoing arcs.

Does there exist a linear time algorithm to find a source in a given directed acyclic graph?

Follow-up question:  Can one in linear time find all sources?

As Yuval mentions, the datastructure is important here. I'll try to give a solution for some of the types of adjacency lists:

Incoming edge list: For each node, there is a list of vertices from which there is an incoming edge to this node. You can simply scan all vertices and check if the size of their adjacency list is $0$  or not. A size $0$ list means no incoming edges, so the node is either a source or disconnected. Assuming a connected graph, this scan of each vertex will give you a list of all sources (or you can stop after finding one) in $O(|V|)$ time - linear in the number of vertices.
Outgoing edge list: For each node, there is a list of vertices to which there is a directed edge from this node. Keep a bit-string with each bit representing a vertex, initialized to 0. Starting from the first node, start scanning its list for vertices to which there is an outgoing edge from this. Every such node (neighbour) cannot be a source, so keep setting their corresponding bit in the bit-string. At the end, all vertices whose corresponding bits are still unset, are the source vertices. You can do this in time linear in the size of the graph - $O(|V| + |E|)$.
Both lists together: For each vertex, there is a mixed list of vertices which have an edge to or from this vertex, with some other attribute indicating which of the two is actually the case. The approach is similar to 2 above, with the addition that any incoming edge immediately rules out the current vertex (and you can mark its bit set). Unlike in point 2 where you need to go through all vertices, here, you might find some source sooner. If you don't stop, you will have all sources. For both cases, time is again linear in the size of the graph - $O(|V| + |E|)$.
Both lists separately: Just pick the incoming edge list and follow 1.

As a side note, if choosing the datastructure is in your hands, you might want to analyze what all operations you intend to perform, and how frequently, and choose an appropriate datastructure.

Edit: For case 1, if you have a dag where the number of sources is very small as compared to $|V|$ (eg, in a tree with one source), and where the average distance from any vertex to a source is small as compared to $|V|$ and you only want any one source, you can use a faster on average algorithm (although worst case asymptotic complexity will be the same). Select any vertex at random, and go to any of its parent (from the incoming edge list), and on to its parent and so on, till you reach a node which has no parent - a source. This small gain of efficiency is for very limited types of graphs with a slightly more complex algorithm.


Algorithm for finding two smallest numbers in an array I was just thinking today that the best approach to find two smallest numbers in any array would be to first sort(ascending order) it with some efficient algorithm like Quicksort(Average case complexity: nlogn) and then access the first two members of the array in O(1).

Is my approach optimal or there are some alternative better approaches?

If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 current smallest and if the new element is smaller, then you replace the larger of the 2 current smallest with the new element. This requires only a few operations per element in the array as you traverse the array, so it's $O(n)$ with a very small constant. It's probably impossible to come up with a sort-based approach that ever runs faster, except maybe for an array of size 4 or 5 or less.


Finding a class of graphs for which vertex coloring is NP-hard We know that for general graphs vertex coloring problem/ minimum clique cover problem are NP-hard and for perfect graphs, they can be solved in polynomial time. There are classes of graphs which are perfect, e.g., bipartite graphs, chordal graphs, linear graphs, etc.

My question is that:

Are there any families of graphs that we know for them vertex coloring problem/ minimum clique cover problem are NP-hard? I appreciate if someone can give the name of some of them or any reference for them (in case they exist).

I have a problem and I want to show that it is hard and I want to find such a family of graphs and use them as an instance for my problem.

This PDF defines a graph for which solving a 3-SAT formula is equivalent to determining if the graph is 3-colorable. Finding the vertex coloring of these graphs would solve the 3-SAT problem, so the vertex coloring problem on these graphs is at least as hard as an NP-complete problem. Therefore, solving the vertex coloring problem on these graphs is NP-hard.


Classifying partially labeled data I have 1D data for binary classification. Data includes about 10000 samples and each sample has the length of 120. Data is only partially labeled (for about 20% of samples, I am sure about the label) and I cannot label samples manually for thoes not labeled. Every ~60 samples come from same recording and therefore belong to the same class. I have tried k-mean clustering and in most cases results matches the labels. What semi-supervised learning algorithm is suitable for this problem?

There are 142 different recordings, each repeated ~60 times. About 20% (28 recording) are labeled. Samples are noisy so I need to average every 5-10 of them. I extracted 10 features based on amplitude of signal for clustering. I expect 60-80% of recordings belong to class I.

One way to interpret this as that it's indicating that points that are nearby in feature space are likely to have the same labels.  So, a classifier that takes this into account might do well.

Based on that, you might try a $k$-nearest neighbor classifier.  Basically, you classify each test point by finding the $k$ most similar labelled samples, and then using some kind of voting scheme among the corresponding $k$ labels.  I anticipate this might give quite good results.

Alternatively, another way to use this is to use some kind of active learning algorithm to help you choose a small subset of the 10000 samples to manually label, with the goal of choosing those smartly so those additional labels help improve the performance of your classifier as much as possible.  One standard approach is to train a classifier on the labelled instances, apply it to all the remaining instances, pick out the 20 instances that the classifier is least confident on, manually label those 20 instances, add them to the training set, and repeat.  In your situation, a possible approach is to train a classifier on the labelled instances, apply it to all the remaining instances, from each cluster randomly sample a few instances whose predicted label disagrees with the majority label for that cluster, manually label all those instances, add them to the training set, and repeat.  Or, you could train both a normal classifier and a $k$-nearest-neighbor classifier on the labelled samples, apply them to all remaining instances, find ones where the two classifiers disagree on their prediction, randomly sample 20 of them (possibly using a farthest-first heuristic to maximize their diversity), manually label them, and add them to the training set and repeat.

You might need to experiment a bit to see what works best.


How binary search works in real world scenario? In binary search, we need an array of integers for it to search for an element. Also, many other sorting algorithm sorts array of integers.

But in real world, we may search for a name of an employee in a database, title of a post etc. So how does binary search actually works in such cases? Is the data converted and stored in some numeric format? Then how does it point to the original record?

Please explain in detail with a small example if possible.

As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.

At least in Java, all we need is data that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I digress, as that is language-specific. It should be clear however that we only need elements to be comparable/order-able. They do not only need to be integers.

You could always, theoretically, use BSTs to model decision making, as you're simply going through Decision A or Decision B at any given point. You'd have to create Decisions that were comparable to one another, but that's fuzzy on my end.

Let me therefore take an example in your post - searching through a database for a name. Of course, names are usually encoded as Strings (a sequence of characters, informally speaking). Strings are usually ordered lexicographically, that is, by alphabetical order. This means that to retrieve a given String from a BST of Strings, we'd start at some root node which contains a root String (consider a String of this database in the M or N range, as that is the middle of the English alphabet), and if the name comes after M/N or before M/N, it will go to the right node or the left node of the root node (containing the middle name), respectively.

Theoretically, you could encode the entire English lexicon into one very large BST, if you have a word that you've set as the exact middle of the English language. Every word that isn't the exact middle word would be coming after or before said word, alphabetically speaking.

I'd point you to this link, about Legislation perhaps being NP-Complete, for some discussions about decision trees. This may be an interesting, albeit not necessarily appliable analogue with BST's: Is legislation NP-complete?

Hope this helps!

EDIT: Edited to say "Prof. Filmus..." as that is more formal.


How to maintain completely dynamic convex hull quickly? If there's no deletion, we can use $2$ balanced trees to maintain $2$ half convex hulls(up and down). In this way, we can insert $n$ points in $O(n\log n)$ time.(In the beginning, there are no points)

A completely dynamic convex hull means that I can insert and delete a point without rebuilding the whole convex hull, which costs $O(n)$'s time.

My problem is, is there any solutions to deleting points quickly? Maybe it could be solved with persistent data structures, but up to now, I haven't come up with any concrete method yet.

This was first solved by Jacob and Brodal in 2002; there is a recent arXiv submission of that work, "Dynamic Planar Convex Hull".


Estimating the complexity of an algorithm by looking at code Time complexity seems rather a difficult notion for people who were not professionally trained in math or computer science. I understand it informally and can high-level compare which one is better and which one is worse (say: polynomial time algorithm is more efficient/faster than exponential time algorithm), but my question is how can one roughly assess the time complexity of his/her own algorithm?

A good example is the grand-canonical problem of integer factorization. Say one tries to write a new method to factor these awfully big integers. We know that the input has x-decimal digits and b-bytes. What does technically make an algorithm inefficient from the start? (say nested loops kills the program already and it's not even worth in-depth measurement? Does one need to obey certain programming rigours in order to ensure time complexity is capped at certain (reasonable) level)?

Sorry if this sounds really informal and amateurish, but I am just very curious about this kind of things, though have little professional knowledge to understand it on my own.

This question is rather informal, and you may enjoy reading this.
What you are asking about is a topic discussed often in Computer Science and Mathematics (perhaps all subjects, but my perspective is not so broad) - "developing an intuition". Often, students are looking for some sort of cheat code to solving problems quickly without going through all of the steps. The honest answer is that you can only develop such intuition and speed by doing precisely the opposite - practicing slowly and without any sort of shortcut.

Practice calculating time complexity - it really isn't too difficult. A quick google search gave me this page, which is pretty informal and may suit the needs of some practice problems. Once you have gone through the process enough times, you will ascend to a sought-after plane of intuition.

Having very little professional knowledge is not an issue. If the example page I sent is too formal, there are plenty of other pages on the web explaining time complexity. You just have to be willing to sit down and put some hours into it (which no different than what a "professional" does to get the same knowledge, except perhaps they pay more for it?).


Skienna's recursive algorithm for edit distance I'm having some trouble understanding part of Skienna's algorithm for edit distance presented in his Algorithm Design Manual. I'm posting the recursive version, prior to when he applies dynamic programming to the problem, but my question still stands in that version too I think.

He provides the following code:

#define MATCH       0
#define INSERT      1
#define DELETE      2

int match(char c, char d)
{
    if (c == d) return(0);
    else return(1);
}

int indel(char c)
{
    return(1);
}

int string_compare(char *s, char *t, int i, int j)
{
        int k;                  /* counter */
        int opt[3];             /* cost of the three options */
        int lowest_cost;        /* lowest cost */

        if (i == 0) return(j * indel(' '));
        if (j == 0) return(i * indel(' '));

        opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);
        opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
        opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);

        lowest_cost = opt[MATCH];
        for (k=INSERT; k<=DELETE; k++)
                if (opt[k] < lowest_cost) lowest_cost = opt[k];

        return( lowest_cost );
}

I am having trouble understanding the logic behind how the indices are decremented when arriving at opt[INSERT] and opt[DELETE]. They seem backwards to me.

How can I prove to myself that they are correct?

The two strings s and t are compared starting from the high index,
down to index 1. This is not visible since the initial call to
string_compare is not provided. The i and j arguments for that
initial call are the length of strings s and t.

It should be noted that s and t could be globals, since they are
the same in all calls.

A call to the function string_compare(s,t,i,j) is intended to
compute the minimum edit distance of the prefixes s[1..i] and t[1..j].
It first compares the two strings at indices i and j, and the
recursively at lower indices.

It always tries 3 ways of finding the shortest distance:

by assuming there was a match or a susbstitution edit depending on
whether s[i]==t[j];
by assuming there is an insertion edit of t[j];
by assuming there is an deletion edit of s[i];

Then it computes recursively the sortest distance for the rest of both
strings, and adds 1 to that result, when there is an edit on this call.

When s[i]==t[j] the two strings match on these indices. Hence the
corresponding indices are both decremented, to recursively compute the
shortest distance of the prefixes s[1..i-1] and t[1..j-1]. A
proper match does not increase the distance. Hence
dist(s[1..i],t[1..j])= dist(s[1..i-1], t[1..j-1]).

When s[i]=/=t[j] the two strings do not match, but can be made to
match by a substitution edit. Hence the same recursive call is
possible, but the resulting shortest distance must be incremented by
one for the substitution edit. Hence dist(s[1..i],t[1..j])=
dist(s[1..i-1], t[1..j-1])+1.

That is why the function match returns 0 when there is a match, and
1 when there is none.

Another possibility is not to try for a match, but assume that t[j]
is due to an insertion edit in the case of the smallest distance.
Hence that inserted symbol is ignored by replacing t[1..j] by
t[1..j-1], ie by computing the shortest distance of s[1..i] and
t[1..j-1], which is string_compare(s,t,i,j-1), and then adding 1
for the insertion edit.

The next and last try is the symmetric one, when one assume that the
symbol s[i] was deleted, and thus does not have to appear in t.

The results of the 3 attempts are strored in the array opt, and the
smallest value of the 3 is kept as shortest distance for s[1..i] and
t[1..j].

The decrementations of indices is either because the corresponding
string elements match, or because they have been taken into account by
an edit operation.


Which non-regular languages are in $AC^0$? For example, I know that the non-regular language $a^nb^n$ is in $AC^0$. I would like to know more examples like this.

Languages in $AC^0$ can be more complicated than naive intuition might suggest.

Obviously, $AC^0$ contains $\{a^n b^n c^n\}$, which is non-context-free.
Every unary language is in nonuniform $AC^0$; for example, the halting problem expressed in unary.
Addition can be implemented in $AC^0$ with a carry-lookahead adder. Here the input is $2n$ bits representing two numbers, and the output contains $n+1$ wires (equivalently, each output bit can be realized in $AC^0$)
Multiplexing: $\{w x: |w|=2^n, |x|=n, w[x] = 1\}$ is in $AC^0$.

A multiplexer is a function on $2^n+n$ variables which outputs the value of one of $2^n$ variables, where the index is determined by the $n$ variables. (The same holds if the index is written in unary.)
Computation of 3SAT formulas is in $AC^0$.

The input consists of $n$ variables, followed by some clauses, each one contains three literals, where each literal is an index of the variable (unary or binary, does not matter) and a bit indicating possible negation. You can evaluate the literals with multiplexers and then add a layer of ORs and then a big AND on top.
$AC^0$ does not contain majority, but it contains approximate majority: a function that is equal to majority if the output is $\geq \frac{1}{2}+ \varepsilon$ zeroes or ones. See "Approximate Counting with Uniform Constant-Depth Circuits" by Ajtai.

$AC^0$ is closed under logical operations, concatenation and composition, so you can combine above examples. Now you should feel some respect for $Parity \notin AC^0$ and other circuit lower bounds!


Calculate winding number How can one calculate the winding number of a polygon given as
a list of vertices in some (counter-clockwise or clockwise) order?

The complexity of the algorithm must be linear time.

The winding number $w$ of a polygon has to be calculated around a certain point $P$. Since your question is ambiguous, I'll suppose you've already determined $P$.

Given a list of n vertices $v_0, v_1, ... v_{n-1},v_0$ (notice $v_n = v_0$) given in counter-clockwise order, a simple linear way to calculate the winding number is
$$
w = \frac {1}{2\pi}\sum_{i=0}^{n-1} \theta_{v_i,v_{i+1}}$$ where $\theta_{v_i,v_{i+1}}$ is the angle between $\vec{v_iP}$ and $\vec{v_{i+1}P}$, which you can obtain using dot product and arcosines.

Your second solution consists of casting a ray $R$ from $P$. The winding number of your polygon can then be calculated as the number of edges $E_+$ that cross $R$ going counter clockwise, minus the number of edges $E_-$ that cross $R$ going clockwise.

I.e.: $w = E_+ - E_-$

If you want further insight (and proof) on how to determine $E_+$ and $E_-$, I highly suggest you research the "point in polygon" problem and the "crossing number" often associated with that problem.


Is there any undecidable language that is countable? All we know is that if a language is countable than it must be recognizable. However, a recognizable language may or may not be decidable.

Your premise is incorrect. The set of all words, $\Sigma^*$, is countable (as long as the alphabet is countable, and we usually refer to finite alphabets anyway).

Every language is a subset of $\Sigma^*$, and thus every language is countable. In particular, there are undecidable and unrecognizable languages.


NP-completeness of Induced disjoint paths In graph theory, it is well-known to be NP-complete the problem of given a set of $k$ pairs of source-sink, deciding whether there exists $k$ vertex-disjoint paths connecting these pairs.

Our problem is a variant in which the requirement of being vertex-disjoint is replaced by being induced.

A set of $k$ paths is said to be induced if:

They are vertex-disjoint.
Each one is itself an induced path.
No edge connects two vertices of two different paths.

  Input: A graph $G(V,E)$ and $k$ pairs of source-sink $\{(s_1,t_1),\dots,(s_k,t_k)\}$

  Output: YES if there exists (a set of) $k$ induced paths connecting $s_i$ to $t_i$ for every $1\leq i\leq k$, NO otherwise.

Is this problem NP-complete?

Your problem is NP-hard (and so NP-complete), by reduction from 3SAT.

Consider a 3SAT instances with variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$.

For each variable $x_i$, there are four vertices $a_i,T_i,F_i,b_i$, connected as follows: $a_i-T_i-b_i$ and $a_i-F_i-b_i$.

For each clause $C_j = \ell_{j,1} \lor \ell_{j,2} \lor \ell_{j,3}$ (where $\ell_{j,1},\ell_{j,2},\ell_{j,3}$ are literals), there are five vertices $c_j,L_{j,1},L_{j,2},L_{j,3},d_j$, connected as follows: $c_j-L_{j,k}-d_j$ (for $k=1,2,3$).
Additionally, if $\ell_{j,k} = x_i$ then we connect $L_{j,k}$ with $F_i$, and if $\ell_{j,k} = \bar{x}_i$ then we connect $L_{j,k}$ with $T_i$.

The source-sink pairs are $(a_i,b_i)$ (for $i=1,\ldots,n$) and $(c_j,d_j)$ (for $j=1,\ldots,m$).

Each $a_i-b_i$ path corresponds to a truth assignment of $x_i$, and each $c_j-d_j$ path corresponds to a choice of a satisfied literal in $C_j$.


Stronger versions of P != NP which better express actual convictions Does the conviction "L-uniform NC1 != NP is incredibly hard to prove!" express the core of "P != NP is incredibly hard to prove!" in a similar spirit as the conviction "The polynomial hierarchy doesn't collapse!" expresses the core of "P is not equal to NP!" ? Let me try to elaborate:

The P vs NP problem implicitly invokes a number of related but distinct challenges and convictions. Focusing on the convictions, we have that NP != coNP is believed with nearly the same conviction as P != NP, and is part of the conviction that the polynomial hierarchy doesn't collapse. (Because the polynomial hierarchy is less familiar than NP, this conviction is weaker, but still strong enough to be used as a reasonable assumption in a proof.)

Similarly, "L != NP is incredibly hard to prove" is believed with nearly the same conviction as "P != NP is incredibly hard to prove". Now there may be weaker statements which we don't know how to prove either, like "$U_{E^*}$-uniform TC0 != PH", but they don't necessarily feel natural enough to be part of real convictions. So my question is whether "L-uniform NC1 != NP is incredibly hard to prove" would qualify as a natural (and sufficiently strong) conviction. (I'm pretty certain that "NC1" is appropriate here, but I'm less certain about "L-uniform" and "NP". Maybe something like "non-uniform NC1 != PH/poly is incredibly hard to prove" would be much more natural and somehow imply all the other related natural convictions.)

Considering that the conviction "P != NP is incredibly hard to prove" is largely based on known barrier results, one promising approach (for answering this question) would be to look for a statement expressing a natural separation, and ask why it is hard to prove. Then one can check which of the known barrier results for P != NP can be extended to that statement.

The question "Why is it hard to prove ALogTime != PH?" should be most promising in this respect. This statement is weaker and more natural than "L-uniform NC1 != NP", because $\subset$ PH and

  ALogTime = DLogTime-uniform NC1 = $U_{E^*}$-uniform NC1 $\subset$ L-uniform NC1.

For the relativization barrier, it would be enough to show ALogTimeA = PHA for  A := TQBF, where TQBF is the PSPACE-complete problem to decide true quantified Boolean formulas. No idea whether the natural proofs and the algebrizing proofs barrier should be expected to carry over, but at least checking whether they do should not be terribly difficult.

I also wonder whether the statement "ALogTime != PH" points to the right place where the difficulties for proving separation results start. Below ALogTime, we have the logarithmic time hierarchy LH, which probably doesn't collapse either, but the question is whether this has been proved (or whether this is relatively easy to prove, just in case nobody cared yet).

Edit: It turns out somebody actually cared to prove that the logarithmic time hierarchy is strict, and how it is related to the AC0 hierarchy. See Searching Constant Width Mazes Captures the AC0 Hierarchy by Barrington et al. I didn't check which results were already proved in one of the references, and which results have been proved for the first time in that paper.

This means that the statement "ALogTime != PH" is exactly the place where the difficulties for proving separation results start. It may be noted that this statement is actually equivalent to "ALogTime != NP", since "ALogTime = NP" would imply "P=NP=PH". Observe that (it seems that) coNLogTime verification can be used instead of PTime verification when characterising NP, so this is actually really equivalent to a statement where "polynomial time" no longer occurs, only some version of "read only polynomial length witness string".


Asymptotic complexity class preservation under logarithm? If $f(x)$ and $g(x)$ are two functions such that

$$f(x) \not\in \Omega(g(x))$$

does

$$\log f(x) \not\in \Omega(\log g(x))$$

hold?

This does not hold for all $f$, $g$. Consider $f(x) = x!$ and $g(x) = x^x$. It is the case that $x! \not\in \Omega(x^x)$ yet, using Stirling's approximation, we have that

$$\log (x!) \in \Theta(x \log x)$$

Since, $\log(x^x) = x \log x$, we have

$$\log f(x) \in \Theta(\log g(x))$$


How to find the smallest of the maximum edges of all paths between two nodes in a graph Say I have an undirected weighted graph G = (V, E), and I have two vertices s and t. Now there may be a number of paths between s and t, and each path has an edge that has the maximum weight in that path. Out of all these maximum weight edges of all the possible paths, how do I find the smallest one most efficiently?

I suppose I could use a modified Dijkstra's algorithm to find all the shortest paths first, while keep record (like an array) of the maximum weight edges of all possible shortest paths, then maybe use linear time selection to find the smallest one. In this case I think I would have a running time of O((|V| + |E|) log|V|). Is this correct and is there a faster way?

Could I use Kruskal's or Prim's algorithm to find the MST of the graph, and then look at all the edges between s and t in the MST to find the largest one? I am not sure if this is correct at all.

In biref, you can just replace addition function with max function everywhere in the typical shortest path algorithm and it will work because they 'behave' the same way and that the algorithm only ever require the weight (together with the aggregation function) to have that 'behaviour'.

More specifically about that required 'behaviour' of weight.
The algorithm only require weight to be any type $\mathbb{W}$ with 'ordered monoid' structure, i.e.,
comes associated with an addition function
$$+\colon \mathbb{W} \times \mathbb{W} \rightarrow \mathbb{W}$$
and with a unique value
$$0 \in \mathbb{W}$$
such that it is associative and unital
$$(a+b)+c = a+(b+c)$$
$$0+a = a+0 = a$$
and finally with a binary (partial or total) ordering relation on $\mathbb{W}$ satisfying
$$x ≤ y \implies z+x ≤ z+y \land x+z ≤ y+z$$
You should check that the correctness proof of the shortest path algorithm only ever utilise these properties.

For fun, you could weight the edges of graph by string, add them using concatenation, have empty string be unit of concatenation, and ordered them lexicographically. Now you can find which path between 2 given points spells out the earliest word in dictionary using shortest path algorithm!


Proving NP Completeness of a subset-sum problem - how? So I'm trying to understand P/NPC problems. The one I'm trying to tackle now is subset sum (we have a collection of integers $S$ and a $k$ param: is there a subset of $S$ that sum of all it's elements is equal to $k$?) problem and the proof that ss is an NPC problem by reduction from 3SAT.

I've found two PDF's that attempt to solve that, but the problem is, I don't have the foggiest idea how to 'explain in in my own words'.

Okay, some links ahead and questions related to them:

Here, on page 4th, there's a logic table for 3SAT clause that apparently proves why ss is NPC, but I don't get it - what exactly are those s and t values, and how does that table proves NPC'ness? And how k is computed in that table? It's simply not clear to me :(

Another link
on pages 5 and 6 there are another tables that appear out of nowhere with no explanation that I could understand.

So, if anybody knows what I'm talking about and could help me, please answer :). Or, if it's possible, can anybode give me a simple and straightforward proof why subset sum is NPC?

The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that is only true if the original 3CNF formula is satisfiable.  Using the 3SAT -> SUBSET SUM reduction from your lecture notes:

The $y$ values encode statements about which variables have positive literals in which clauses.  The $z$ values encode statements about which variables have negative literals in which clauses.

The $s$ value is crafted the same way for each clause; put a one in the digit position corresponding to that clause, and zeroes everywhere else.  The $t$ value will be the same as the $s$ value for each clause.

The $k$ value is always 1111... followed by 33333.... where the number of ones is the same as the number of distinct variables in the formula and the number of threes is the number of clauses in the formula.  Note that the required sum $k$ has a one in each digit position corresponding to the variables.  This means that any solution to the subset sum problem can include only encoded statements about either a positive instance of the variable or a negative instance in each clause, not both.  Note also that sum $k$ has a three in the digit position corresponding to each clause.  The $s$ and $t$ values for each clause will sum to two, but to complete the sum a third one will have to come from one of the $y$ or $z$ values.  All three ones could come from the $y$ and $z$ values, but the fact that $s$ and $t$ will only sum to two for any clause guarantees that any empty clause in the 3CNF formula forces the subset sum problem to become unsatisfiable.


Example of exponential algorithm performing better than a polynomial one? I have a weird question.

I was just wondering if there were some problem with two solutions; one (A) being exponential time, the other one (B) being polynomial time. However the constants involved are such that, in "practice", the algorithm (A) performs better.

For instance, we could have something like $(1 + 10^{-100})^n$ versus $n^{10^{100}}$.

(I said exponential vs. polynomial, but any other distinction would do.)

I think the classic example of this is in Linear Programming.

The Simplex Algorithm is exponential time, but fast in practice. There is a polynomial time algorithm, but it's generally slower.

See the relevant Wikipedia entry.


3/2 - Approximation probabilistic algorithm for MAX-3-COLOR I have a textbook question here regarding Max-3-Coloring and need some assistance with it. I have searched for any type of information regarding it but haven't found anything substantial. Here is the question:

  In MAX-3-COLOR you are given a graph $G=(V,E)$ and your goal is to
  find a coloring of the vertices with only 3 colors $c: V \rightarrow
 [3]$ that maximizes the quality function $q(c)$ - The number of edges
  whose endpoint vertices are colored with different colors:

  $\sum_{(i,j)\in E} (1_{c(i) \neq c(j)})$

  Give a probabilistic $3/2$-approximation algorithm. (i.e $q(c)\geq 2/3 \cdot OPT$
  with probability at least $1-\frac{1}{e^{k}}$ for any $k \in \mathbb{N}$

OK so up until now the textbook only talks about one probabilistic algorithm which fits the requirements - MAX-3-SAT. The textbook gives a probabilistic $8/7$ - approximation algorithm for it (for every literal, toss a fair coin and decide whether to set it to $True$ or $False$).

I also found several other sources which prove that the 3-COLOR is NP-Complete by reducing it to the 3-SAT problem. Thus I am pretty confident that MAX-3-SAT is the way to go.

According to this thread: 3 Colorability reduction to SAT I thought about doing the same thing:

  For every $x \in V$ create three literals: $x_1, x_2, x_3 \in \{{True,
 False}\}$ where each literal denotes if said vertex $x$ is colored
  with color $i$.

  Then for every edge $e =(x,y)\in E$ create the following
  3-CNF formula $\varphi$:

  $ \varphi_e = (\urcorner x_1 \vee \urcorner y_1 \vee \urcorner y_1)
 \wedge (\urcorner x_2 \vee \urcorner y_2 \vee \urcorner y_2) \wedge
 (\urcorner x_3 \vee \urcorner y_3 \vee \urcorner y_3) \wedge (x_1 \vee
 x_2 \vee x_3)$

  And the final formula $\phi$ is:

  $\phi = \bigwedge_{e \in E} \varphi_e$

Every 3-CNF formula for an edge makes sure that the two endpoints are not of the same color and that one of them is either color 1, 2 or 3.

The thing is I don't see how this would help me. This gives me a MAX-3-SAT problem since I have a 3-CNF formula for every edge and one big 3-CNF formula for the whole graph. So technically I could use the same algorithm that was given in the textbook before

But wouldn't using the same probabilistic probabilistic $8/7$ - approximation algorithm for the MAX-3-SAT give the exact same approximation? whereas I wish to achieve a $3/2$- approximation

Thanks to anyone who helps!

If you simply uniformly at random (i.i.d) color each of the vertices of $V$ by each of the three possible colors, then for every edge $e\in E$, it's endpoint will be colored by different colors w.p. $\frac{2}{3}$, hence the expected quality of the random coloring is exactly $\frac{2|E|}{3}$. We know that the optimal quality is at most $q^*\leq |E|$, hence this is a $\frac{3}{2}$ approximation.


How to recognise the number of errors that can be detected and corrected of a large set of codewords (k) each having a specified number of bits (n)? I am struggling to find how can I know the number of errors that can be corrected and detected using (n=10) bit code with a (k=550) codewords.
As far as I know, to calculate the number of errors to be corrected and/or detected someone must know the Hamming distance between 2 codewords. However, I do not have any relevant information to find out a solution to this question. I tried to calculate the efficiency of this code using the formula:
(E = Number of original message bits / length of the codeword). The efficiency in my case is 1/5. But, I do not know how can I use this information to calculate the number of errors that can be corrected and detected.

There are $2^{10}$ binary strings of length $10$. We can partition them into pairs $x_1\ldots x_90,x_1\ldots x_91$. Since your code contains more than $2^9$ codewords, it will contain at least one such pair. Hence the minimum distance of your code is only $1$.


Efficient Median Algorithm With Very Constrained Operators What is the most efficient algorithm for finding the median of an array when the available operations are limited to Max(), Min(), Multiply, Add, and no conditionals are allowed. Pivots and sorts are not allowed. The algorithm I have come up with so far seems very inefficient and goes like so:

For an array of length n, create a working array of length 2n by
doing pairwise Max() comparisons for every pair of elements in the input
array. This 2n array is guaranteed not to contain the lowest value from the original (or one fewer of the lowest value if there were ties for the lowest value)
Recursively call (1) n/2 times
Take min() of final array

There's got to be a faster algorithm!

I can get you an improvement for the first step; every time you do that first step, you're basically trying to find the minimum, and then continue on the rest of the array. You don't need to do all that just to find the minimum; instead of making that large array (which sounds like it contains $\binom n 2$ elements, not $2n$, unless I misunderstood you), you can basically do the following:

Starting from the left, take every pair of consecutive elements, and put the minimum of the two on the right. Something like this in pseudocode:

temp1 = min(array[i], array[i+1])
temp2 = max(array[i], array[i+1])

array[i] = temp2
array[i+1] = temp1

What will happen is that the minimum element gets moved all the way to the far right using $2(n-1)$ mins and maxs. We can then do our recursive call on the first $n-1$ elements, and repeat until we finally pull out the median.1

1 Some of you reading this will note that basically what we end up with is a bubble sort (reverse in the example I gave) where we stop as soon as we figure out the median. If you decide to move the max to the right instead, then we pretty much are doing a normal bubble sort, but stopping once we get the median.


Is there way to compare computing power used in two blockchains when every one of them is using different mathematical function as a Proof-of-Work? If I am a Bitcoin node, I can evaluate two blockchains in terms of each one consisting of more Terahashes than the other and thus deduct which one is the "correct" one. There is impartial source of consensus - hashes done. But what if I had two blockchains, each one making a different function, e.g. one is Bitcoin and making SHA-256 and another is making other random computation. Could I impartially deduct which "chain" has the most computation power spent even if in those two chains the "way" this computation power is spent is different? Is there common impartial denominator then?
Or, to make it even more interesting, if a blockchain had self-amending possibility like Tezos, and in a certain point of time it reached a consensus to change it's Proof-of-Work method to e.g. more memory-hard (in order to discontinue usic ASICs) then could a node that wasn't connected to the network before that change somehow use a common denominator of computing power (now not necessarily Hashes used) to evaluate the right chain by checking how much computing power was spent on chain both before the amendment (when e.g. SHA-256 was used) and after change (when some new Proof-of-Work is used)?

Short answer - no. Any denominator used to compare computing power spent on two different functions would be subjective to those functions. Therefore it cannot be source of consensus spreading over many functions. It'd like comparing apples to oranges.


Draw a DFA that accepts ((aa*)*b)* A homework question asks me to a draw a DFA for the regular expression

$((aa^*)^*b)^*$

I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s many times, in terms of a DFA.

I would guess it that $(aa^*)^*$ should be the same thing as $\lambda + a^*$ but I'm not sure if I can formally say that. If I could, it would make my DFA simply

I recommend you first try to understand the language denoted by the regular expression. Once done this can make it easier to build the DFA directly . If you can not think of how to build the DFA you can always turn your regular expression into an NFA and then the NFA into a DFA(Convert regular expression to DFA).

The strings denoted by your regular expression are:

   Empty string or a concatenation of strings formed by a chain of zero or more $a's$ followed by a $b$. This mean that your initial state should be a final state too and a word in this language "always"(except  $\epsilon$) finish with a letter $b$ so your DFA can't transition to a final state consuming a letter $a$. I hope those hints can help you to generate your DFA directly.


Is the number of coin tosses of a probabilistic Turing machine a Blum complexity measure? I read that the number of coin tosses of a probabilistic Turing machine (PTM) is not a Blum complexity measure. Why?

Clarification:

Note that since the execution of the machine is not deterministic, one should be careful about defining the number of coin tosses for a PTM $M$ on input $x$ in a way similar to the time complexity for NTMs and PTMs. One way is to define it as the maximum number of coin tosses over possible executions of $M$ on $x$.

We need the definition to satisfy the axiom about decidability of $m(M,x)=k$. We can define it as follows:

$$
m(M,x) =
\begin{cases}
k & \text{all executions of $M$ on $x$ halt, $k=\max$ #coin tosses} \\
\infty & o.w. \
\end{cases}
$$

The number of random bits that an algorithm uses is a complexity measure that appears in papers, e.g. "algorithm $A$ uses only $\lg n$ random bits, whereas algorithm $B$ uses $n$ random bits".

Probabilistic "functions" are not even functions in the classical sense of the term "function", that is, they do not assign to each member of the domain a specific member of the range. They are not even partial functions.  So the requirement of the Blum axioms that the complexity functions be computable cannot be satisfied.

Specifically, for a TM $M$ with input $x$, the Blum axioms require an algorithm that for input $(M,x,n)$ decides if $\Phi(M,x)=n$, where $\Phi$ is the complexity measure.  But if $\Phi(M,x)$ is a probabilistic function, then it cannot be computed by an algorithm, and there also can be no algorithm as required by the axioms.

We could, however, define a complexity measure differently on probabilistic models, allowing a random variable, which is after all, a kind of function.  Then various properties of the r.v. -- mean, median, standard deviation, etc -- could well qualify as complexity measures, and you could develop the theory from there, in the probabilistic/statistical realm.

So, although Blum measures are somewhat out of favor, except for the classic space and time measures, there's no inherent reason the basic idea can't be extended in ways like this.


Are there languages generated by linear grammar which aren't regular? Are there languages generated by linear grammer which aren't regular?

Of course. Look at the first example on Wikipedia:

$\qquad S \to aSb \mid \varepsilon$

is linear and generates $\{a^nb^n \mid n \in \mathbb{N}\}$, a non-regular language.

If you mean left-linear, or right-linear, then no - they are equivalent to REG.


What is the minimum number of parts required to split the sequence S to in order to obtain sequence T? Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a
number (possibly one) of continuous parts. For each part independently, I then choose any integer
value and removes all occurrences of this value in the corresponding part (note that there could be
no such occurrences). After that, the person will combine all parts in the same order to achieve a new
sequence (T).  How to find out the minimum number of parts needed to split the sequence in order to achieve this goal .
 let n = size of sequence S and m = size of sequence T

Constraints: 1 <= n,m <= 2000

Input Format: n m  Sequence S   Sequence T

Output Format: if it is not possible to transform S into T output -1  otherwise, output min number of parts required.

Sample Input and Output:

Input
Output

4 24 2 7 24 7
1

7 24 7 1 4 1 7 14 7
3

3 27 4 24 7
-1

My Attempt:
I did not understand how Sequence S={4,2,7,2} can be transformed to T = {4,7}. If I followed this procedure by splitting a sequence into parts such as {4} {2} {7} {2} and then iterate from 1st index and then the 2nd index until the end, and if I encounter the same value I delete all of its occurrences. When I do this, I get  the sequence {4,2,7} and minpart is just 1.
And, for the sequence {4,7,1,4,1,7,1}, I am able to get {4,7,1} and minparts are 3.
But I do not understand, how both of these sequences: S = {4,2,7,2} and S = {4,7,1,4,1,7,1} can be transformed to the sequence T = {4,7}?

To get the sequence $T = \{4,7\}$ from $S = \{4,2,7,2\}$, you can take the entire set S as a minipart and remove $2$ from it. Therefore, there is just one minipart.

To get the sequence $T = \{4,7\}$ from $S = \{4,7,1,4,1,7,1\}$, you can take three minimarts as follows:

$P1 = \{4\}$
$P2 = \{7\}$
$P3 = \{1,4,1,7,1\}$

Now, remove $4$ from $P1$, remove $7$ from $P2$, and remove $1$ from $P3$. You will get the sequence $T = \{4,7\}$.


The finer details of Meek's STV Meek's version of the Single Transferable Vote system [.pdf] is used in multiple big elections including those of New Zealand and Stack Exchange.

Demonstration (with thanks to the Department of Internal Affairs of New Zealand).

I have a basic understanding of how the votes are counted, but there's one thing I haven't been able to figure out.

What happens if positions are left blank?

For example:
Assume 6 candidates and no limit on the amount of choices.

One could vote (where left is first vote and right is last): 3 4 5 6 1 2 or 4 5 6 and leave the rest blank.

In the STV system, the following is legal as well: 0 2 4 0 1 6
What would happen in that case?

Will the choices be shifted to clear it from any left-open positions or will the votes be counted at the moment indicated by the position? Those options will (likely) influence the election both in different ways.

I'm not a CS expert in any way, just trying to get the hang of an interesting system to implement my own vote counter.

In Meek STV, there is the concept of the quota or threshold that a candidate must exceed to be considered elected. This threshold is changed from round to round in the Meek STV system. The threshold changes based on how many votes are thrown away.

Let's say that your code is 4 5 6 and the rest blank, then once all those candidates are either elected or eliminated, the remaining part of your vote is considered "thrown away". Based on this, the threshold is changed for what candidates need to be elected in the next round.

In the STV system, the vote 0 2 4 0 1 6 is considered the same as 2 4 1 6 0 0, i.e. the zeros are automatically put at the end.

In the Stack Exchange moderator elections, it is possible to choose only a second candidate and a third candidate, but not a first. That is the same thing as choosing a first candidate and a second candidate.

Related on Meta Stack Exchange: How are moderator election votes counted, in pure English?


Convert given string to Palindrome with given substring Given a String S1 and String S2. Convert string S1 to a palindrome string such S2 is a substring of that palindromic string. Only operation allowed on S1 is replacement of any character with any other character. Find minimum number of operations required.

Here is a description of a simple brute force approach that works in $O(n^2)$, where $n$ is the length of $S_1$.

Let $m$ be the length of $S_2$. If $m>n$, return -1 immediately, indicating impossibility.

Keep a counter on how many characters will be changed. Change $S_1$ so that its substring with length m that starts at index 0 is the same as $S_2$. Mark the indexes where characters have been changed. Also chang $S_1$ so that ist substring that starts at index n-1-0 and goes backwards to index n-m-0 is $S_2$ backward. However, abort this try if we have to change the characters that has been marked. Now change the remaining characters of $S_1$ to make it a palindrome. That is, if the character at index $i$ is not same as the character at index $n-1-i$, change the later to be the former. Once done, the counter tells us how many changes is needed to make $S_1$ a palindrome that has $S_2$ as its substring starting at index 0.

Repeat the above with index 0 replaced with index $1, 2, \cdots, n-m$, keeping tracking of the minimal number of changes.

The above description should be enough to set you up. You may want to improve it or look for better algorithms.


After stereo image rectification, why does the relation between disparity and depth still apply? The relation between disparity and depth is derived based on the assumption that the two cameras are parallel.

Image rectification does not make this assumption valid.

But I see in many university computer vision lectures, with two rectified images, the depth map is directly calculated.
I cannot figure out why.

Image rectification does not make this assumption valid.

Yes it does!

From the wiki: https://en.wikipedia.org/wiki/Image_rectification

  Image rectification warps both images such that they appear as if they have been taken with only a horizontal displacement and as a consequence all epipolar lines are horizontal.

The term can be used in an overloaded manner though, by instead implying that projective distortions from the camera are removed. So you have to be careful.


If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$ How to prove if $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$ ?

it means every recursive set is mapping reducible to set $B\neq \aleph$. I really have no idea to prove this.

UPDATE

$A,B$ are sets, $A \leq_m B$ if there is a computable function $f$ such that

$A = \{ x \in N | f(x) \in B\}$

Since we have $A \leq_m B$ and $A$ is recursive, it means checking membership (characteristic function) in $A$ is recursive, so it means checking $f(x) \in B$ is recursive, right?

I guess it means $B$ must be recursive too and it means every recursive set is mapping reducible in to every other recursive set. Am I right?

This should be a comment on the original post by @Drupalist and on Ds D's answer, but it's too long. It's not enough to say that $A\le_M B$ requires $B$ be recursive or that one of $B, \overline B$ be r.e.

Let $A$ be recursive and $B=\{(\langle\,M\,\rangle,\langle\,N\,\rangle)\mid M,N\text{ are TMs and }L(M)=L(N)\}$. This language (sometimes called $\text{EQ}_{\text{TM}}$) is known to be neither r.e nor co-r.e. However, let

      M(x) =                    N(x) =
         return accept             if x = 0
                                      return reject
                                   else
                                      return accept

We have $(\langle\,M\,\rangle,\langle\,M\,\rangle)\in B$ and $(\langle\,M\,\rangle,\langle\,N\,\rangle)\in \overline{B}$. Then if $A$ is recursive, there is a decider TM, $D$, for A and if we define $f$ by

      f(x) =
         run D on x
         if D(x) = accept
            return (<M>, <M>)
         else
            return (<M>, <N>)

Then $f$ is Turing-computable and $x\in A\Longleftrightarrow f(x)\in B$, which is the definition of $A\le_M B$. So we can have such a reduction in every case where it's possible to find (not necessarily by a TM) two instances $y\in B$ and $n\in\overline{B}$.

Note that I'm not claiming that this technique will work for all possible $B$ nor am I claiming that this technique is the only possible one. All I've shown is that the problem isn't as simple as it seems at first glance.