Data structure to use for a consumable message queue where it's safe for messages to overwrite one another I have a queue of messages representing filesystem operations that need to be processed in order. A message may succeed or fail when it's sent. A change message, for example, is generated when a user creates or saves a file.

Delete Foo.txt message sent
Delete Bar.txt message sent
Change Baz.txt message sent
Change Foo.txt message sent

In the most common case, I pop the top item from the queue and send it off for processing, which succeeds.

But suppose this happens:

Delete Foo.txt message attempted (FAIL)
Delete Bar.txt message attempted (OK)
Change Baz.txt message attempted (OK)
Change Foo.txt message attempted (OK)

What should I do in this case?

I want to move on and process the next item in the queue, but it's not that simple. In this case, "Delete Foo.txt" must be processed before "Create Foo.txt", otherwise we're deleting Foo.txt from the search index (see "more details" below), even though it exists.

One approach I had considered: a key-value store, where the document path is the key, and the Message is the value. In the context of a filesystem, the only operation that matters is the most recent, so overwriting the Message associated with a file if it hasn't been sent might work.

What kind of data structure and algorithm is right for this situation? I don't want to reinvent the wheel.

A few more details:

New items are constantly arrive in the queue, from multiple producer threads
The messages are consumed from the collection by a single consumer
A message is a serialized object, sent to a RabbitMQ broker
This queue exists in case the RabbitMQ broker goes down or a Publisher Confirm fails
Messages are consumed from the endpoint by a different service which performs various actions to keep a search index incrementally up to date
C#, if it matters

Update 1:

Big picture

I am sending messages about filesystem operations that have occurred. These messages are used to keep a search index (elasticsearch) up to date. A few minutes behind is perfectly acceptable. If a user makes three saves in rapid succession, I don't need search index updates for the first two saves. (If it happens, that's fine, but it's not required.)

CRUD operations are done by users working with their files on a busy network share. Each write operation triggers a message that has to be sent to a persistent work queue (the RabbitMQ broker). An example message might contain data that boils down to "File F has been deleted" or "File Y has been changed". (No file contents are contained therein.)

(These messages are consumed by another component downstream that performs an action based on the contents of the message, which is outside the scope of this question.)

Because messages represent filesystem actions that were performed in a sequence by users they either:

Have to be sent in order so they can be processed in order OR
The message associated with the most recent write operation on File F should overwrite any queued message associated with File F that hasn't been sent yet

In my example above (second unordered list), it's safe for the message representing "Change Foo.txt" to overwrite a failed "Delete Foo.txt", because the Change message was triggered after the Delete message. (The time where Foo.txt didn't exist isn't important.) Hence my thought of a using key-value store of  as a holding area in case of a Message send failure.

Sorry, you have to tell us more.  We can't tell you what you should do in case of a failure; that will depend upon the application semantics and the type of a failure.

In general, in the event of a failure of an attempted operation, there are several options:

Retry the operation later.
Treat the failure as permanent.

If you decide you want to retry it later, then the implications of this for other operations depends on the dependencies between operations and the desired semantics.  If operations A and B commute (performing A first then B has the same effect as B then A), and if you try A and it fails, then often you can perform B immediately and then retry A.  If operations A and B don't commute, and you try A first and it fails, then performing B immediately and then retrying A will have different semantics, which might or might not be acceptable depending upon what guarantees you are trying to provide.

Related topics: ACID, database transactions.

Example: Suppose you have a one-level filesystem (with no directories), and the intended semantics are that operations on one file can be performed in an arbitrary order compared to operations on another file (but operations on a single file are performed in the order they were requested).

Then operations A and B commute if they are performed on different files, and they don't commute if they're performed on the same file.  Thus, conceptually you can maintain one queue per file.  When you receive a request to perform operation $O$ on file $F$, append $O$ to the queue for $F$.  Whenever you are free to perform an operation, pick an arbitrary file whose queue is non-empty and try the operation at the head of the queue.  If the operation succeeds, then you can pop it from the queue.  If it fails and you want to retry it later, then you have to leave it at the head of the queue to be retried later.

Such a data structure can be implemented with a hash table of queues. The hash table is keyed on the filename; it yields a queue.  It's easy to implement all the necessary behaviors using this data structure.

I am assuming that there are only two possible outcomes of an attempted operation: success (the operation is performed in full), or failure (and there is no effect: this is the same as a no-op).  If it is possible that an operation can fail partway through without rolling back its effects, so it has a partial effect, then you've got much bigger problems.


Computer Networks, OSI model What layer of OSI model does define the route of information transmission between sender and receiver computers?

A) Session layer
B) Physical layer
C) Data link layer
D) Network layer
E) Transport layer

In this question I think answer must be Network layer.But my teacher insists that answer is Transport layer.Even though i have shown in so many books it was written like that:

"Path Determination. The network layer must determine the route or path taken by packets as they flow from a
sender to a receiver. The algorithms that calculate these paths are referred to as routing algorithms."

this is from book that name is "Computer Networking: Top-Down approach, 5th edition,James Kurose",

chapter 4.1.Introduction and Network Service Models

The Transport layer offers services as:

Connection-oriented communication
Same order delivery
Reliability
Flow control
Congestion avoidance
Multiplexing

The network layer is responsible for packet forwarding including routing through intermediate routers.

The answer is definitely Network layer.


What is the average height of a binary tree? Is there any formal definition about the average height of a binary tree?

I have a tutorial question about finding the average height of a binary tree using the following two methods:

The natural solution might be to take the average length of all possible
paths from the root to a leaf, that is

$\qquad \displaystyle \operatorname{avh}_1(T) = \frac{1}{\text{# leaves in } T} \cdot \sum_{v \text{ leaf of } T} \operatorname{depth}(v)$.
Another option is to define it recursively, that is the average height for a node is the average over the average heights of the subtrees plus
one, that is

$\qquad \displaystyle \operatorname{avh}_2(N(l,r)) = \frac{\operatorname{avh}_2(l) + \operatorname{avh}_2(r)}{2} + 1$

with $\operatorname{avh}_2(l) = 1$ for leafs $l$ and $\operatorname{avh}_2(\_) = 0$ for empty slots.

Based on my current understanding, for example the average height of the tree $T$

    1
   / \
  2   3
 /
4

is $\operatorname{avh}_2(T) = 1.25$ by the second method, that is using recursion.

However, I still don't quite understand how to do the first one. $\operatorname{avh}_1(T) = (1+2)/2=1.5$ is not correct.

There is no reason to believe that both definitions describe the same measure. You can write $\operatorname{avh}_1$ recursively, too:

$\qquad \displaystyle \operatorname{avh}_1(N(l,r)) = \frac{\operatorname{lv}(l)(\operatorname{avh_1}(l) + 1) + \operatorname{lv}(r)(\operatorname{avh_1}(r) + 1)}{\operatorname{lv}(l) + \operatorname{lv}(r)}$

with $\operatorname{avh}_1(l) = 0$ for leaves $l$. If you don't believe that this is the same, unfold the definition of $\operatorname{avh}_1$ on the right hand side, or perform an induction proof.

Now we see that $\operatorname{avh}_1$ works quite differently from $\operatorname{avh}_2$. While $\operatorname{avh}_2$ weighs the recursive heights of a nodes children equally (adding and dividing by two), $\operatorname{avh}_1$ weighs them according to the number of leaves they contain. So they are the same (modulo the anchor) for leaf-balanced trees, that is balanced in the sense that sibling trees have equally many leaves. If you simplify the recursive form of $\operatorname{avh}_1$ with $\operatorname{lv}(l) = \operatorname{lv}(r)$ this is immediately apparent. On unbalanced trees, however, they are different.

Your calculations are indeed correct (given your definition); note that the example tree is not leaf-balanced.


What is the difference between R precision and precision at K? I am trying to understand the difference between these two but it looks like as if they are calculated the same way. What is the difference?

R precision:

  R precision is the precision at the Rth position in the ranking of results for a query that has R relevant documents.

Precision at K:

  Precision at K is calculate for only K documents. Documents ranked lower than K are ignored.

R-Precision

R-Precision is defined as $\frac{r}{R}$, which is the ratio between all the relevant documents retrieved until the rank that equals the number of relevant documents you have in your collection in total ($r$), to the total number of relevant documents in your collection $R$.

Suppose in your collection there are 100 documents in total, 30 of which are relevant ($R = 30$), the rest irrelevant. So you retrieve the first 30 documents (because 30 are relevant in total in your collection) and, say, 10 of them are relevant ($r = 10$). Your R-Precision is then $\frac{10}{30} = \frac{1}{3}$.

Precision@K

Precision@K is defined as the precision at rank $k$, which is more intuitive if you know about the definition of precision itself. Suppose your system retrieves 10 documents, where the relevant ones are at ranks ${1,3,6,7,9}$ and you want to know how 'well' your system does until rank 5 ('well' depends on the objective of your system of course but here we'll say we want high precision at low ranks). So you compute your Precision@5, which is the ratio of the number of relevant documents until (including) rank 5 to the total number of documents until $k$ (this number is $k$ itself). Your Precision@K where $K = 5$ is therefore $\frac{2}{5}$.

Youc an see that R-Precision is a measure that allows for assessment of your entire system whereas Precision@K really only takes the documents until $K$ into account. Depending on what you want to measure, either of them may be suitable.


How does casting really work for primitive data types? I have written the following C code which purpose it is to flip an unsigned number in binary representation and give back an unsigned number:

long flippingBits(long n) {
    return (unsigned)(~n);
}

int main(){
    long a = flippingBits(someNumber);
    ...
}

This code does work fine. What about this code?

unsigned long flippingBits(long n) {
    return (~n);
}

int main(){
    unsigned long a = flippingBits(someNumber);
    ...
}

This code indeed prints out negative numbers. WTF. This is beyond my intuition. So is there an (architectural) way, to explain this phenomenon? How does the casting of primitive data types work?

Casting of primitive datatypes works in a very simple way:

  Under the hood, values don't have types. Casting does absolutely nothing.

As a simple example, let us consider casting 65 to an ASCII character, thus obtaining the symbol A. What happens under the hood? Absolutely nothing. The only thing that changes is how the program treats the value. When it thinks of it as an integer, it sees 65; when it thinks of it as an ASCII character it sees A.

The CPU does accommodate different datatypes when performing various operations. For example, it has separate instructions for signed and unsigned integer arithmetic, and for floating point arithmetic. Moreover, there are different instruction for different lengths (i.e. 16-bit vs. 32-bit vs. 64-bit for integers). But it is up to the programmer to instruct the CPU which instruction to use. The CPU doesn't keep track of datatypes, which are a higher-level concept.

Modern CPUs do keep a distinction between code and data to some extent, for security purposes. But otherwise the semantics of data is up to the programmer.

Sometimes casting does have an actual effect, and this is during promotion. When casting an integer to a floating point number, or a 32-bit integer to a 64-bit integer, the program calls some instruction which effects this conversion (in the second case, the exact instruction depends on whether the integer is signed or unsigned).

When casting a signed integer to an unsigned integer of the same length (or vice versa), probably nothing happens. This is exactly your case.


Algorithm to check two binary expression trees for equivalence Is there any known algorithm to check for equivalence of two binary expression trees over a field $\mathbb{F}$?
For example for the expression $a+b = b+a$ it should return true (since $\mathbb{F}$ is commutative) and $a^b = b^a$ should return false as well as for $a^2 = a$.
I can think of a naive implementation which is basically brute-force creating all equivalent binary expression trees for LHS and for RHS and check for a non empty intersection.
Is there a real-world-efficient algorithm to do this? I mean it isn't a must to be polynomial time but will work fast for common or relatively small problems (trees with at most ~100 nodes).
Wikipedia doesn't give any reference to the problem of comparing two for equivalence over some algebraic structure.

The answer depends heavily on what operations you allow to appear in the trees.
If the tree uses only addition, subtraction, and multiplication, this is an instance of the polynomial identity testing problem, which can be solved in polynomial time by a randomized algorithm.  Basically, you pick random values for $a,b$ and check whether both trees return the same value; and repeat a few hundred times.  See https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma and Is there an efficient algorithm for expression equivalence?.
Division can also be handled by expressing the tree as a rational polynomial (ratio of two polynomials), then again using polynomial identity testing.
If you can have addition, subtraction, multiplication, division, and exponentiation, then I don't know whether there are efficient algorithms.  I think that problem, or some variant of it, is addressed here: Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials.

(Possibly loosely related: Decidability of Equality of Radical Expressions)
Let me also highlight that expressions like $a^b$ "smell fishy" and don't typecheck when $a,b \in \mathbb{F}$ are elements of a finite field.  For instance, if $\mathbb{F}=GF(p)$, then exponentiation $a^b$ is well-defined if $a$ is taken modulo $p$ and $b$ is taken modulo $p-1$ (not modulo $p$).  In particular, $(a+p)^b=a^b$ modulo $p$, but $a^{b+p} \ne a^b$ modulo $p$.  So, to make an expression like $a^b$ make sense, $a^b$ has to be interpreted as $a^{f(b)}$ where $f$ maps from elements of $GF(p)$ to numbers $\{0,1,\dots,p-2\}$.  There is a natural way to do that, e.g., $f(0)=0$, $f(1)=1$, ..., $f(p-2)=p-2$, $f(p-1)=0$.  But then when you do that, exponentiation doesn't have the properties you might expect.  In particular, $a^{b+c}$ is no longer equal to $a^b \times a^c$.  For instance, if $b=1$ and $c=p-1$, then $a^{b+c}=a^{p-1+1}=a^0=1$, but $a^b = a^1 = a$ and $a^c = a^{p-1} = 1$, so $a^{b+c}=1$ but $a^b \times a^c = a$.  So I would be pretty suspicious of any expression that contains exponentiation where the expression in the exponent is an element of $\mathbb{F}$.


Proving that English is not a regular language I am wanting to try and prove that the English language is not regular.
The alphabet is the set of all words in the English dictionary.

Looking at sentences, I was able to use this pattern of sentences

{ [ (determiner) (noun)]n (verb)n where n is >= 1} ⊆ of the English language

and  { [ (determiner) (noun)]m (verb)n where m  ≠ n}  ∩ of English

determiner is anything like the, my etc.
Noun is any noun and verb is also any verb.

All three of these (determiner, noun, and verb) are finite and disjoint. Would something like pumping lemma be a good way to approach this?

It is not easy to prove the complexities of natural languages. See Complexity of natural languages for some hint that English language is not regular.

In fact in Evidence Against the Context-Freeness of Natural Language,
Stuart M. Shieber shows that many natural languages are not even context-free.

However, I only know about Dutch and a dialect of Swiss German, for which proof of non context-freeness exists. And the proofs are quite old, the results about them were proved in 1980s.

For detail you can also refer - The Handbook of Computational Linguistics and Natural Language Processing
edited by Alexander Clark, Chris Fox, Shalom Lappin.


How do 2-3 FingerTrees generalize to bigger branching factors? FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to amortize per-node overheads better, or to improve lookup performance at the cost of update performance.

For example, we might want branching factors of 31-32 as in RRB-trees, or branching factors of 16-32 as in B-trees. How should the size of the Digits change to accommodate these branching factors? More generally, are there algebraic conditions on the size ranges of Nodes and Digits which are sufficient to guarantee the asymptotics (logarithmic access to the middle; constant-time access to the ends) of FingerTrees?

Yes - if you read the original paper and assign the notions of safe and dangerous digits to the smallest and largest digits, the math should all go through.


Is $(aaaaa)^n aa (aaaaa)^n$ a regular language? Is the language $\lbrace (aaaaa)^n aa (aaaaa)^n \mid n \in \mathbb{N} \rbrace$ regular? It looks like I need infinitely many states so it is not regular.

The language consists of those strings that contain $5 n + 2 + 5 n = 10 n + 2$ symbols $a$ for some $n \in \mathbb{N}$, i.e.,
$$\lbrace(aaaaa)^n aa (aaaaa)^n \mid n \in \mathbb{N}\rbrace =
\lbrace (aaaaaaaaaa)^n aa \mid n \in \mathbb{N} \rbrace.$$
It is regular because it is accepted by the automaton which has twelve states $s_0, \ldots, s_{11}$ with a starting state $s_0$, accepting state $s_2$, and transitions $s_i \stackrel{a}{\longrightarrow} s_{i+1}$ for each $i = 0, \ldots, 10$, and one more transition $s_{11} \stackrel{a}{\longrightarrow} s_0$. In essence, this automaton counts the number of letters modulo 10 and accepts if the answer is 2.


Find minimum number of time points that cross out all intervals Say we have a set of time intervals, that may intersect. A time point "marks" all of the intervals that are still unfinished at that time point. I wish to find an algorithm so that I can mark all of the intervals using the least amount of time points. E.g. if all of the intervals have not finished at time 6, one point is enough, as point 6 it marks all of the intervals of the problem. Starting and ending time points ( [s(i),e(i)) ) for each interval i are given. Time points are integer values.

The point i marks intervals that have started before i and finish after i, or intervals that started exactly at i.

Obviously, I would like something better than plain out trying all possibilities.

I have tried a greedy algorithm, more specifically choosing the point that marks the most intervals at a time (it is easy to see that it is only worth considering points at which an interval starts), removing the intervals it marks and repeating with the remaining intervals. I have found counter-examples showing it does not always give correct results.

The next try would be dynamic programming, which I am breaking my head with right now. However it gets too complex. In the recursive calls I have to make a call for the possibility that the time point checked will be included, and one for the possibility that it will not. However, I must find a way to select a time point anyway, in the case not selecting it will lead to intervals not being marked at all - in that case, I must recognize that before proceeding to the next recursive calls, as I will get false results. It also is a problem how I will keep a record of which intervals proceeded to the recursive call unmarked, without taking too many actions that will increase complexity.

Interval graphs might give me some ideas. If we are talking about interval graphs the problem can be expressed like this: Suppose we have a graph. The nodes are NOT the intervals, but the starting points of each interval. If a starting point of an interval 1 intersects with an interval (at any of its points) interval 2, then its node is connected to the starting point node of that interval 2 with a directed edge. Choosing to mark a node removes the said node and all the nodes it is connected to. What is the least number of markings I must execute in order to erase the whole graph?

Hint:

   Try some more greedy algorithms; keep trying, and don't give up yet.  You might try solving some small examples by hand, to get some intuition for what is going on, and see what strategies you end up developing.  The way to look for a greedy algorithm is to try all greedy strategies you can think of -- it's not enough to just try one particular strategy and if that doesn't work give up on the entire paradigm of greedy algorithms.

This looks like a nice learning exercise, so keep at it.  You can do it.  (We're glad to help you understand concepts but just solving this exercise for you probably won't help with that.)


Branch and Bound explanation I have a test about the branch and bound algorithm. I understand theoretically how this algorithm works but I couldn't find examples that illustrates how this algorithm can be implemented practically.

I found some examples such as this one
but I'm still confused about it. I also looked for travelling salesman problem and I couldn't understand it.

What I need is some problems and how can these problems solved by using branch and bound.

Let's apply Branch and Bound to Knapsack, hopefully this will make the concept clear to you.

We have $n$ items, labelled $1$ through to $n$. $v_i$ is the value of the $i$th item, and $w_i$ its weight. We try to fit them in a knapsack that can contain up to $T$ weight in total, and we try to maximize the sum of the values of the item we put in the knapsack.

The ordinary backtrack approach is our basis. We first put $v_1$ in the pack, and then solve the problem for the remaining $n-1$ items with recursion. We then remove $v_1$ from the pack and solve the problem for the remaining $n-1$ items again, and we return the best configuration that we've found.

This backtracking is the 'Branch' part of Branch and Bound. You branch on (in the case of Knapsack) two cases: 'item $i$ is part of the solution' and 'item $i$ is not part of the solution'. You can visualize this as a binary tree, where the left child is one case and the right child is the other case. This tree is the search tree (or search space): its depth is $n$, and it therefore has $O(2^n)$ nodes. The algorithm therefore has a running time exponential in the number of items.

Now we get to the 'Bound' part: we try to find criteria such that we can say 'this configuration never work out, so we might as well not bother computing this'. An example of such a criterion is 'the weight of the items we've already put in the knapsack exceeds $T$': if we've added, say, the first $n/2$ items to the knapsack and it is therefore already full, there's no point trying to put items $n/2+1$ through to $n$ in the knapsack as well, but there's also no point in trying to fit any subset of $n/2+1$ through to $n$ in the knapsack, as it's already full, so we save about $2^{n/2}$ cases. Another example is 'even if I put in all the remaining items, the value of the items I've put in will not exceed the best configuration I've found so far'.

These criteria essentially cut away parts of the search tree: at some node, you say for instance 'the left subtree will not give me a better configuration, because X', so you forget about that subtree and you don't explore it. A subtree of depth $d$ that you cut out this way saves you $O(2^d)$ nodes, which can be quite a bit of a speed increase if you're lucky.

Note that this is called 'Bounding' because it usually involves some kind of lower or upper bound: for the criterion 'even if I put in all the remaining items, the value of the items I've put in will not exceed the best configuration I've found so far', the value of your best configuration so far is a lower bound on the best configuration, so anything that will never make it past this lower bound is doomed to fail.

You can make the 'Bounding' part as complex as you like. For instance, integer programming problems are often solved using relaxations: you relax your program to a linear program, which you can solve in polynomial time, and then you can throw away a lot of cases for your binary variables that will never work out anyway. You then branch on the remaining options.

Note that Branch and Bound usually only gives you a speed increase in practice, but not in theory: it's hard to say exactly how much of the search tree is cut out using your heuristics. This is testified by the number of different heuristics used in practice on such problems. If you're unlucky, the remaining search tree remains huge even with a lot of bounding.


Understanding Alpha Beta Pruning: Why do we ignore the values of a unsearched tree after the first leaf, can they not include acceptable values too? So this is my question.

I am trying to understand this part of the book:

At d) why do we stop looking at the other nodes in that branch? There could be a acceptable value next to the 2? I am just trying to understand alpha beta pruning for a while.

At $d)$, minimizer is comparing the $2$ he found with the currently best option for the maximizer higher in the tree (at node $A$, where maximizer will choose between $B$,$C$,...), which is $3$, at node $B$. He then knows that maximizer will not choose $C$.

The node $C$ will have value $2$ when minimizer sets it and would have value $2$ or less if minimizer explored it fully, so he doesn't need to waste his time searching other branches from $C$ if he already knows that maximizer will not choose anything lower than $3$.

I think what confuses you may be the following:
You are imagining a real-life gameplay scenario, but this is different in the sense that minimizer and maximizer must play their best move and will calculate it correctly.
So there is no way that minimizer could in this situation "fool" maximizer by setting the wrong value of $C$ (something higher than $3$) to force maximizer to choose it. If we assume that scenario a possibility, we must also implement the maximizer with "free-will" so he may not choose his best option but this is no longer an $\alpha$-$\beta$ pruning :)


Can we count the number of times a particular state in a DFA is running in a loop? If in a particular DFA , we are looping in a state for n symbols.... Is there any way to keep track  of this 'n'?

First of all, let me mention that the definition of DFA is final. The definition specifies everything that counts as a DFA. If you modify the model, it is no longer a DFA. However, your question makes sense if we interpret it as trying to change the model while keeping the class of languages accepted by the model.

There are several ways to interpret counting. If you could keep track of the number of loops through a state and then still remember it when you exit the state, then (depending on your exact rules) you could accept the language $a^n b^n$. So any mechanism that allows this is ruled out.

Another interpretation is that the state keeps a loop counter $C$, and it can base its decisions on the value of $C$ (that is, allow the transition function to depend on the auxiliary information $C$). This is also too powerful – you can accept every unary language (i.e., a language over $\{0\}$) using this mechanism.

What if we just allow the state to remember some information about $L$? Say that we partition $\mathbb{N}$ (the natural numbers) into finitely many sets $S_1,\ldots,S_d$, and we want to allow our transitions to depend also on which class $C$ lies in (here it doesn't really matter whether we are counting how many times we were at a state overall, or in the current run).

Let's do the case $d=2$ first. We can think of this as defining a unary language $L$ (which we identify with a subset of $\mathbb{N}$), and allowing transitions to depend on whether $C \in L$ or not. In this case, the resulting automaton model (for some fixed $L$) remains equivalent to DFAs precisely if $L$ is regular (exercise).

The general case is similar, and left to the interested reader.


show that special case of NP-complete problem is also NP-complete? I want to show that a problem is NP-hard by reducing a known NP-complete problem to it. However, I will have to use a special case of the NP-complete problem for the reduction to work. I'm pretty sure that the special case version is also NP-complete but I have no idea how to prove that. Are there any general guidelines for how to do this?

For example, consider this version of the SUBSET SUM problem without repetition:

Given an integer I and a multiset S of integers in the range 1,2,...,10, is there a non-empty subset of S whose sum is I?

I could be wrong, but don't think the restriction of possible values in S to {1, ..., 10} affects the NP-completeness of the problem. How would one go about showing this?

EDIT: Apparently that version of the problem is actually in P. I might restate my question later.

"Are there any general guidelines for how to do this?"

Frequently, one does that by reducing from the general case to the special case.

Otherwise, being a special case of a known NP-complete problem isn't really helpful for that.

How would one go about showing this?

Due to dynamic programming, one would prove  P = NP .


CFGs: detecting infinitely many derivations of a single string Some particularly degenerate CFGs can produce a single string in infinitely many ways: for a dumb example, $S \to SS \mid \epsilon$ can produce the empty string as $S \to \epsilon$ or $S \to SS \to S \to \epsilon$, etc.

I'm writing a general CFG parser which can produce all the different parses for a given string, but obviously it chokes on examples like the above. I'd like to be able to detect when there may be infinitely many parses for a string, rather than just looping forever. Can I, and, if so, how?

My intuition is that a grammar has this property if and only if there is some non-useless nonterminal A (ie, A is used in the production of some string in the language of the CFG) which can produce itself via some chain of productions such that all of the other symbols produced by following that chain are nullable nonterminals of A itself. But I don't know if this is correct, and I'm not sure how to detect it.

(A nonterminal B is nullable if $B \to^* \epsilon$, ie, some series of productions replaces the symbol with the empty string.)

If a nonterminal can derive itself ($A \to A$) then you can have an infinite number of derivations deriving whatever else that nonterminal can derive. There is no need for it or any other nonterminal to derive $\epsilon$ (unless you are only concerned with an infinite number of parses for the empty string.)

In other words,

$$A \to A \mid a$$

can produce infinitely many parses for the string $a$. By contrast,

$$A \to A A \mid a$$

can only produce exponentially many parses for the string $a^n$.

As far as I know, the existence of a useful nonterminal which can (possibly indirectly) derive itself is necessary and sufficient for the existence of an infinite number of possible parses.

It's easy to detect whether a nonterminal can derive itself. First, use the standard algorithm to find all nullable nonterminals. Then define the relation
$$ R = \{ (A, B) \mid A \to \omega B \chi \wedge \omega \to \epsilon \wedge \chi \to \epsilon \}$$
which you can do in linear time by scanning all the productions keeping track of nullability.

Then construct $R^+$. If it contains $(A, A)$ for any nonterminal, you have a possibly indirect self-derivation.


LTL globally implies I have got confused in undressing the informal definition of LTL below: $$G(\phi \Longrightarrow\psi)\Longrightarrow(G\phi \Longrightarrow G\psi)$$

in many literatures I have seen implies is said as replies like for LHS we can say Always/Globally $\psi$ replies to $\phi$. is it correct?
Does the LHS implies the RHS if so what is the informal interpretation of the formula? (Alway $\psi$ replies to Always $\phi$) replies to (Always $\psi$ replies to $\phi$)

You seem to be pretty confused, so let's sort some things out.
First, it's "implies", not "replies". That is, the formula $\phi\implies \psi$ means that if $\phi$ holds, then $\psi$ holds.

To be more precise, the formula $\phi\implies \psi$ is true in one of two cases: either $\phi$ is false, in which case we say that the implication is vacuously true, or if both $\phi$ and $\psi$ are true.

Now, in LTL, the operator $G$ means that something holds in every position in the computation.
Let's examine the two "sides" of your formula with respect to that.

The formula $G(\phi\implies \psi)$ means that in every point of the computation, the formula $\phi\implies \psi$ is true, in the form mentioned above.

The formula $G\phi\implies G\psi$ means, as above, that either $G\phi$ is false, or both $G\phi$ and $G\psi$ is true.

Now it is fairly easy to see why the formula you have is true: if $G(\phi\implies \psi)$ is true, then, if $G\phi$ is true, then $\phi$ is true in every position, but then according to the LHS we have that $\psi$ is also true in every position, so $G\phi\implies G\psi$ is true.

For your second question, an informal way to think about this (there are many others, probably) is this: if you require that whenever $\phi$ holds, then $\psi$ must also hold, then in particular, if $\phi$ is always true, then $\psi$ is also always true.


What are examples of applications of the tree decomposition of a graph? I am looking for specific applications of the tree decomposition (of a graph), because I want to motivate its existence. What are examples of problems that are more easily solvable using the junction tree of a graph (rather than tackling the problem directly on the graph)? Please, provide also the references to the papers or books that mention these specific applications.

An example of an application of the junction tree (or tree decomposition) of graph is described in the paper Junction Tree Variational Autoencoder for Molecular Graph Generation (2019), by Wengong Jin, Regina Barzilay and Tommi Jaakkola.


How can I get all representations of an n-ary tree that completely "cover" the tree? I have an n-ary tree and I want to get all possible representations of the tree that "cover" (for lack of a better term) the tree. Here's what I mean by cover:

Suppose we have the following tree

        1
     /    \
    2      3
   / \    /|\
  4   6  5 7 8
      |
      9

I want to somehow obtain the following:

1
2, 3
2, 5, 7, 8
4, 6, 3
4, 6, 5, 7, 8
4, 9, 3
4, 9, 5, 7, 8

As you can see 1 completely covers the tree because all leaves are underneath it. Similarly 2, 3 covers the entire tree because all leaves are underneath them. This goes for all of them until finally we get to 4, 9, 5, 7, 8 which covers the entire tree because all leaves are underneath (or are them).

Is there an algorithm to do this or a modification of a classic search algorithm that will produce this?

Let $T$ be a tree with root $r$, and let the children of $r$ be $r_1,\ldots,r_d$. Then every minimal cover of $T$ either consists of $r$, or is a union of minimal covers of $r_1,\ldots,r_d$; if $r$ is a leaf then the second option doesn't exist. You can easily convert this to a recursive algorithm that lists all minimal covers.


Is the difference between between an union and a product of two DFA lies in their accepting states? It seems to me that in order to construct the union and the product of two DFA we use basically the same method.

The difference is that when we make the accepting states for the resulting DFA. Suppose $A_{1}$ an DFA with $F_{1}$ as an accepting state, and $A_{2}$  an DFA with $F_{2}$ as an accepting state. In the case of an union of $A_{1}$ and $A_{2}$, the accepting states have either $F_{1}$ or $F_{2}$ or both, and in the case of a product, the accepted state is {$F_{1},F_{2}$}. Am I correct?

Please use the terminology correctly. The union operation is an operation defined on sets. It does not make sense to speak of the union of two automata.

The product construction can be used to give a constructive proof that the class of regular languages is closed under union. But with minor modifications, the product construction can also be used to show that the class of regular languages is closed under intersection as well as under set difference.

Assume that we have two DFA $M_1 = (Q_1,\delta_1,\Sigma,q^1_0,F_1)$ and $M_1 = (Q_2,\delta_2,\Sigma,q^2_0,F_2)$. In the case of intersection, define the set of accepting states as

$$F = \{ (q_1,q_2) \mid q_1 \in Q_1 \wedge q_2 \in Q_2 \} $$

For set difference, define the set of accepting states as

$$F = \{ (q_1,q_2) \mid q_1 \in Q_1 \wedge q_2 \notin Q_2 \} $$


Clarification about big Oh calculation Say you have a loop that iterates over an array,

for i in someArray:
    //some code

This basic example would have a running time of $O(n)$. Say that you added a nested loop with equal number of operations, this then would be $O(n^2)$. My question is, is it safe to do this kind of simplication in general? For example,

Say your outer loop had worst case complexity of $O(n^2)$ and your inner loop has worst case complexity of $O(\log n)$. Can the total time complexity be said as $O(n^2\log n)$?

Your first generalisation is wrong, it depends on what's the complexity of loop content. However if that 'some code' is of constant complexity [something like $O(1)$], the whole complexity will be $O(n)$.

Your second example is correct.


How to find a function in Lambda Calculus? Yesterday I have been trying to complete this exercise. I have to find:
$$ ((map)l)t \simeq \lambda k \lambda x ((k)(t)t_1)....((k)(t)t_n)x $$

where $$l=\lambda k \lambda x ((k)t_1)....((k)t_n)x$$
And $t$ is a generic Lambda term.
I tried but without success.
Maybe it will be something like that :
 $$map=(\lambda a \lambda b (\lambda s \lambda d((b(st))d)))$$
Thank you in advance to all will answer

In your attempt,

$$map=(\lambda a \lambda b (\lambda s \lambda d((b(st))d)))$$

$a$ plays the role of $l$, $b$ the role of $t$, $s$ the role of $k$, and $d$ the role of $x$.

So, $b(st)d$ should actually play the role of $l(kt)x$, but here we see some mismatch: $b$ does not represent $l$, $a$ does that. Also, we can not use $t$, but must use $b$ instead.

Hence, the correct answer seems to be $a(sb)d$. We get (using the standard notational shortcuts)

$$map=(\lambda a b s d.\, a(sb)d)$$

Try to check whether $map\, l\, t$ does $\beta$ convert to the intended term.

Your original idea, namely using $kt$ instead of $k$, seems to be the right intuition, as far as I can see.


Is plain multiplication a P problem? I am a CS novice who just recently encountered the P vs NP problem. And I was wondering whether plain multiplication is a P problem. If it is, does that mean there is a polynomial relationship between the increasing complexity and the time required to solve? I.e. Is there a polynomial relationship between the time required to solve x*1, x*2, x*3, x*4, etc?

I tried to get some "experimental results" by writing simple a Java program that multiplies BigIntegers and counts time of execution. Curiously, I noticed that the execution time only increased in a polynomial manner (e.g. 2ms -> 4ms -> 6ms, etc) when the "complexity" grew in a exponential manner (e.g. x*2 -> x*20 -> x*200, etc), meaning that time and execution of multiplication is a logarithmic relationship instead? Why is this?

Thanks in advance.

Yes, and with many different algorithms.

See https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

One important thing to notice is that the size of the input is the number of digits in the numbers, rather than the magnitude of the numbers (e.g. the "size" of the number 657 is 3, rather than 657, because it has 3 digits).


How can divide by 2 blocksize bubblesort followed by a final mergesort be optimized in a particular environment? I am wondering if we had a large array to sort (let's say 1,048,576 random integers), chosen because it is a perfect power of 2, if we can just keep dividing those blocks into smaller and smaller half size blocks, how would someone know (on a particular computer using a particular language and complier) what the ideal blocksize would be to get the best actual runtime speed using mergesort to put them all back together?  For example, what if someone had 1024 sorted blocks of size 1024, but it could that be beaten by some other combination?  Is there anyway to predict this or someone has to just code them and try them all and pick the best?  Perhaps for simplicity they would want to use some simple bubblesort on the 1024 size blocks, then merge them all together at the end using mergesort. Of course the mergesort portion would only work on 2 sorted blocks at a time, merging them into 1 larger sorted block.

Also, what about the time complexity analysis on something like this?  Would all divide and conquer variations of this be of the same time complexity?  The 2 extremes would be 2 sorted blocks (of size 524,288) or 1,048,576 "sorted" blocks of size 1, handed over to a merge process at that point.

The normal way to tell is through measurement: we try different choices for the threshold, benchmark each one, and choose the best.  This can be tricky, as the best threshold might vary from computer to computer (depending on, e.g., the relative speeds of CPU vs RAM, the size of various caches, and so on).  So, a plausible approach might be to benchmark on multiple different platforms and then choose one threshold that seems to do ok on most of them.

Asymptotic running time analysis probably won't be very helpful, because the constants matter a lot; and because the cache/memory hierarchy probably matters a lot, and standard running time analysis doesn't model the memory hierarchy very well.


Advantages of FPGAs over GPUs What are the advantages of using FPGAs over GPGPUs? It seems like GPGPUs have the best of CPUs and GPUs combined.

There are specific applications for which GPUs are useful. For example, they are useful when we want to perform same operation(use same instructions) but for many different data elements in parallel. For example, add 1K elements in parallel. Such workloads are said to have Data Parallelism.

This is not the case with FPGAs. They are highly customisable and can be made to do anything you want and not just highly data parallel operations. Hence, FPGAs offers much more freedom for designers than GPUs.


is it always true that the depth of BFS is $\leq$ DFS? I have a simple theoretical question in very basic algorithms, as the title mentions, is it always true that the depth of BFS is $\leq$ DFS?

From what I understand, the tricky part here is the possible cycles in the graph. Even though that I believe that the depth of BFS will always be less or equal to the depth of DFS.

In each iteration of BFS, from what I understand, the depth might grow by one, but DFS's grows in each vertex it can not reach, sometimes above the maximal value of BFS.

So, is it always true that the depth of BFS is $\leq$ DFS?

A result about BFS is that what you call the depth of the BFS of a node $v$ is the length of a shortest path from the source to $v$.

Assume the exists an instance where the depth of the DFS $<$ BFS. Then we have a path from the source to $v$ that has length strictly smaller (the path taken by the DFS to reach $v$) than the length of a shortest path from the source to $v$ (the path taken by the BFS), which is impossible.

This argument by contradiction shows that depth BFS $\leq$ DFS, for any graph.


Need help with previous "Automata / Theory Of Computation" exam question I passed by this question in a previous exam while studying for the "Automata / Theory Of Computation" and I am struggling to find answer. I would appreciate it if someone can help me with it:

This is the question:

a)On the basis of what was covered in class, draw the Venn diagram representing the following sets:

1.REXP: the set of the language given by all regular expressions

2.DFSA: the set of all languages recognized by deterministic FSAs

3.NFSA: the set of all languages recognized by non-deterministic FSAs

4.CFG: the set of all languages generated by context free grammars

5.PDA: the set of all languages recognized by PDAs

The relevant set-theoritic relations are
$$
\mathsf{REXP} = \mathsf{DFSA} = \mathsf{NFSA} \subsetneq \mathsf{CFG} = \mathsf{PDA}.
$$
The corresponding Venn diagram consists of two circles, one inside the other.


How to generate branch tables from SSA form? Branch tables are usually described as an efficient way a compiler can implement a switch statement, and that actually seems how GCC and Clang do it (and LLVM even has an opcode just for that).

If a sequence of if statements is used (instead of a switch), GCC doesn't seem to generate a table, but Clang still does.

Given a compiler that turns the code into basic blocks inside a control flow graph in static single assignment form, how would it decide where to generate tables? Is there any research on that? I'm particularly interested in finding an algorithm for lowering consecutive branchings (found on the CFG/SSA form) into a branch table (as Clang seems to do).

(I actually tried looking for any papers about that but didn't find anything.)

Edit: I do understand that the obvious way to do this is to expand the definition of the SSA to include multiple branchings as a primitive (i.e., blocks may branch to an arbitrary number of blocks); I'm wondering if (and how) the tables could be done in a simpler definition, where each basic block may move to at most two other blocks (i.e., only unconditional moves and an if branching).

The book "A Retargetable C Compiler: Design and Implementation" by Christopher Fraser and David Hanson gives some detail on how they lower switch statements to a combination of conditional branches and jump tables. They cite prior work that their technique builds on, so it would be a good start for a literature survey.

There should be nothing particular to SSA that makes generating jump tables harder or easier. An SSA IR like LLVM can include an explicit instruction for an N-way branch, so that generation of jump tables is really about how to lower such an instruction.

(Update: you've edited the question in a way that makes it clear this isn't really about generating jump tables, but rather about re-discovering switch-style control flow from cascading if statements in an IR. This is again probably not specific to SSA. You might look at the "Relooper" algorithm as implemented for Emscripten which deals with more general control-flow restructuring. I'm not aware of a reference specific to recovering N-way branches, but it seems like simple ad hoc approaches should work well.)


Cores, threads and sockets: what does it mean the calculation $T = tcs$ and the number on windows task manager performance? Well, suppose then we have an CPU system such as:

Thread(s) per core $\equiv t$ :    4
Core(s) per socket $\equiv c$:    4
Socket(s) $\equiv s$:             1

Then, we must to perform a simple calculation such as: $ 4 \cdot 4 \cdot 1 = 16 $
Therefore, in general we have:
$$ T = t\cdot c \cdot s \tag{1}$$
I guess that the equation $(1)$ gives you then the total number of threads which your system can handle simultaneously.
On the other hand, consider the figure, of windows task manager, in the following:

In the red box we clearly see the number of "Threads". So I would like to know:
What is the difference between the number given by formula $(1)$ and the number given by windows task manager?

There are two kind of threads, hardware and software threads. The threads number shown in red box is the number of software threads. The threads calculated above(16) is the number of hardware threads.
A processor consists of multiple functional blocks like, register sets, integer ALU, floating point ALU, instruction decoder, instruction fetch units... In a pipelined processor supporting superscalar architecture (also known as hyperthreading or HT on Intel processors), instructions from multiple software threads can be in different phase of execution at the same point of time. The number of software threads instruction sequence which can be concurrently executing in a single processor core is defined by the hardware and are known as logical threads. Look at SMT threads for more clarity.
The number of threads shown is red box or software threads are the total number spawn threads. At most, 16 of them can be executing at the same point of time on the specified hardware. Operating system schedule software threads (in 1000's) on the available processors using some scheduling policy.


Largest rectangle problem Recently while solving programming challenges for the fun of it, I encountered a challenge which left me kind of puzzled and yearning for a proper solution, other than brute forcing. The problem (stated in my own words) is as follows:

In each testcase you are given N (6 <= N <= 10) sticks.
Each stick has length L (1 <= L <= 20) provided. The lengths are represented by space separated integers.
Print the maximum area that can be created by forming a rectangle from these sticks.
Example input:
1 // testcase count
6 // number of sticks
1 1 2 2 3 1 // lengths

I have managed to solve this problem using brute-force method (which's complexity I didn't dare estimate), stacking multiple for loops and lots of if conditional statements.
However, I believe there must be some algorithm that would be suitable for this kind of a problem - there usually is one smart solution in those algorithm puzzles.
I tried to think of a solution for the past few days and didn't come to any meaningful conclussion.
I would greatly appreciate any suggestions - I don't need no code or ready solutions, only a hint about whether there is some algorithm that could be used here to make the solution more elegant, and with better computational complexity than a simple brute force.
EDIT
You are supposed to form 4 edges of a rectangle. Sticks can be stacked on top of each other to form a longer stick. Eg.

a1 = 2+2
a2 = 3+1
b1 = 1
b2 = 1
a*b = 4

The problem is to maximise the value of a*b.

Unfortunately this problem is NP-hard, so no computer scientist knows (or is admitting that they know! :-P) a way to solve it in time polynomial in the number of sticks.  Don't feel bad about using brute-force here -- it's essentially the best you can do.

First, let's reframe the rectangle problem as a decision problem, that is, a problem to which the answer is either YES or NO:

Rectangle: Given a multiset $Y = (y_1, \dots, y_m)$ of stick lengths and an area threshold $k$, is it possible to build a rectangle from the sticks in $Y$ having area at least $k$?

Squares are optimal solutions when they exist

Before getting into the reduction, we will need a property about what a maximal solution to the Rectangle problem looks like.  Under the constraint that $a+b=c$, $ab$ is maximised precisely when $a=b$, i.e., squares have uniquely maximum area among all rectangles of fixed perimeter.  You can verify this by substituting $b=c-a$ into $ab$ and then differentiating w.r.t. $a$: the derivative becomes zero at $a=c/2=b$, and this is clearly a maximum since the coefficient of the $a^2$ term is negative.  The practical significance of this fact is: If and only if it is possible to partition the stick lengths into 4 equal-size subsets, then the maximum-size area achievable is $s^2/16$, where $s$ is the sum of all stick lengths.

Reduction from Partition

I'll show this is NP-hard by reducing the NP-hard problem Partition to it.  In Partition, we are given a multiset of $n$ integers $X=(x_1, \dots, x_n)$, and our task is to partition this multiset into two parts having equal sum.

Given an instance $X=(x_1, \dots, x_n)$ of Partition, with total sum $t=\sum x_i$, we construct an instance $Y = (y_1, \dots, y_{n+2})$ of Rectangle by taking each $x_i$ as a stick length $y_i$, and adding two more "big" sticks, $y_{n+1}$ and $y_{n+2}$, both of length $t/2$.  (That is, $m=n+2$.)  Finally, we set $k$ to $t^2/4$.

If the answer to the constructed Rectangle problem instance is YES, then by the maximal-square property, it must be possible to partition $Y$ into four equal-sum parts, each having sum $t/2$.  Let $(A, B, C, D)$ be such a partition.  Two of these four multisets must each contain a "big" stick and nothing else, since the big sticks have to go somewhere, and combining one of them with any other sticks would mean that one side exceeds $t/2$, meaning that some other side must fall short of $t/2$, meaning that the rectangle is not square and thus of size strictly less than $t^2/4$ -- a contradiction.  Remove these two big sticks, leaving two remaining multisets of sticks, which must also be of equal sum (that is, also $t/2$): these two multisets represent a valid partition of the original $X$ into two equal-sum parts, showing that the answer to the original Partition instance is also YES in this case.

In the other direction, if the answer to the original Partition problem is YES, meaning that there is a way to partition $X$ into two equal-sum parts $U$ and $V$, then clearly the answer to the constructed Rectangle problem instance is also YES: We could simply use the four multisets $U$, $V$, $\{y_{n+1}\}$ and $\{y_{n+2}\}$.

Since a YES to either problem instance implies a YES to the other, it must also be that a NO to either instance implies a NO to the other: in other words, the answers to both problems are always the same.  And since the Rectangle problem instance can be constructed in polynomial time from the Partition instance, any algorithm that can solve Rectangle in polynomial time could also be used as a subroutine to solve Partition (any, by extension, every other NP-hard problem) in polynomial time.  Since Partition is an NP-hard problem, this implies that Rectangle is too.


Can the pseudo-random-sequence generator be described as a finite state automaton? I am thinking some real examples of FSAs in order to help me know how to use the model of the FSA. As I know, the pseudo-random-sequence generator should be a kind of DFAs or FSTs . But I cannot describe a pseudor-andom-sequence generator (e.g. LFSRs) by using $(Q, \Sigma, \delta, q_{0}, F)$.

Specifically, the input of the pseudo-random-sequence generator is the seed which is a short string. However its output is a long (or even an infinite) string. Maybe we   need construct a FSA with a clock, but I have no idea. And what is  $F$ (the set of final states) here? I cannot image what is the language of a pseudo-random-sequence generator.

A finite-state automaton can output an unending sequence of outputs, so you don't need to do anything special.  The regular language will contain all prefixes of possible output streams.

If you really want to consider infinite strings, you could use  Büchi automata to model that. Personally, I don't see the point.


What does apostrophe-like symbol in the superscript mean? It's hard to look up the meaning of a symbol if you don't know what it is called in the context that it is written.

That apostrophe-type symbol in the sequence notation - what is that?

That's a prime.

  In mathematics, statistics, and science, the prime is generally used to generate more variable names for things which are similar, without resorting to subscripts – $x'$ generally means something related to or derived from $x$.


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

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

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

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

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


Find a minimum-cardinality Hall-violator Given a bipartite graph $(X,Y，E)$, in which there is no perfect matching, I want to find a smallest subset that violates Hall's condition, i.e., a minimum-cardinality set
$S \subseteq X$ for which $|N(S)|<|S|$.

This problem is the optimization version of a former question Finding a subset in bipartite graph violating Hall's condition, from which I know there exists a polynomial-time algorithm for finding such $S \subseteq X$. Does there exists a polynomial algorithm for the optimization problem?

This is not an answer - just a long note.

The question is related to the problem of Minimum vertex cover with minimum overlap of one side .
Suppose we have a minimum vertex cover $C$ of size $m$. By Konig's theorem, $m$ also equals the size of the maximum matching, so $m < n$.

Since $C$ is a vertex cover, any vertex not in $C$ must have all its neighbors in $C$. So $N(X\setminus C)\subseteq Y\cap C$. Hence:
\begin{align}
|N(X\setminus C)|
&\leq |Y\cap C|
\\
&= m-|X\cap C|
\\
&= m-n+|X\setminus C|
\\
&< |X\setminus C|
\end{align}
so $X\setminus C$ is a Hall-violator.
Now, if $X\cap C$ is large, then $X\setminus C$ is small.

However, I am not sure that finding a $C$ which maximizes $X\cap C$ also yields the smallest Hall violator.


Using 2-opt Heuristic in a Genetic Algorithm for TSP I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (https://arxiv.org/ftp/arxiv/papers/1209/1209.5339.pdf) and I saw in the same paper that he uses the 2-opt heuristic (and the 3-opt one) on every new child, so I went ahead and did the same.

Using this definition of the 2-opt (https://en.wikipedia.org/wiki/2-opt) I implemented their following pseudo-code:

  repeat until no improvement is made {
       start_again:
       best_distance = calculateTotalDistance(existing_route)
       for (i = 1; i < number of nodes eligible to be swapped - 1; i++) {
           for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
               new_route = 2optSwap(existing_route, i, k)
               new_distance = calculateTotalDistance(new_route)
               if (new_distance < best_distance) {
                   existing_route = new_route
                   goto start_again
               }
           }
       }
   }

The problem with my class is that it takes way too much time when tested on a 51 cities instance (not to mention that 1 generation takes more than 20 minutes in the a280 instance)..

Is there a better approach to this algorithm? A faster/more robust way of improving the new children?

One optimization to your pseudo-code is to calculate the new cost of a route after performing a 2-opt move by:

cost = cost - d[b(i)][i] - d[i][a(i)] - d[b(k)][k] - d[k][a(k)] + d[b(i)][k] + d[k][a(i)] + d[b(k)][i] + d[i][a(k)]

with $b(x), a(x)$ being the node before and after node $x$ on your current route.


Show that a decidable language is not decided by a decider in a given set M.Sipser's Introduction to the Theory of Computation offers the following problem in its chapter on decidability:

Let A be a Turing-recognizable language consisting of descriptions of Turing machines, {⟨M1⟩,⟨M2⟩, ...}, where every Mi is a decider. Prove that some decidable
language D is not decided by any decider Mi whose description appears in A.
(Hint: You may find it helpful to consider an enumerator for A.)

My qualm about this is that the question seems to imply finding a decidable language, the decider for which is not in the set of all deciders, which goes against the definition of decidability of languages.

Could you explain whether my doubts are justified? And if not, could you provide a proof (or a sketch of a proof) for the given problem (with or without the enumerator that is mentioned in the hint)?

Suppose that $A$ is a recognizable set containing descriptions of always halting Turing machines. We want to show that there exists a decidable language $L$ such that for any $M$ deciding $L$ we have $\langle M\rangle\notin A$.

We can construct such $L$ via simple diagonalization. Assume $A$ is infinite (otherwise the problem is trivial). We will define a Turing machine $M$ such that $L(M)$ does not have a decider in $A$. Let $M_A$ be an enumerator of $A$. Given input $x$, $M$ executes $M_A$ untill it outputs the $|x|'th$ word in the enumeration $\langle M_{|x|}\rangle$. Now, execute $M_{|x|}$ on $x$ and flip its answer.

I leave it to you to show that $M$ always halts and that $L(M)$ disagrees with $L(M_i)$ on at least $2^i$ inputs, where $M_i$ is the i'th Turing machine in the enumeration of $A$.


Median of medians: bound on pivot position If I understand correctly (from reading Wikipedia), median-of-medians pivot selection makes quickselect $O(n)$ because the pivot is guaranteed to be in between the 30th and 70th percentiles and so at least 30% of elements will be removed in each selection pass.

But I have tried to prove this percentage inductively but failed. In fact, I have found what I thought is a counterexample (where $\vec{v} \times n$ repeats $\vec{v}$'s elements $n$ times and $+$ is concatenation, as in Python lists):

\begin{align}
\begin{bmatrix}
1 & 2 & 3 & \infty &\infty
\end{bmatrix} \times 3 +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2
\\+ \begin{bmatrix}
4 & 5 & 6 & \infty &\infty
\end{bmatrix} \times 3  +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2\\
+ \begin{bmatrix}
7 & 8 & 9 & \infty &\infty
\end{bmatrix} \times 3  +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2\\
 + \begin{bmatrix}
10 & 11 & 12 & \infty &\infty
\end{bmatrix} \times 3 +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2\\
+ \begin{bmatrix}
13 & 14 & 15 & \infty &\infty
\end{bmatrix} \times 3 +  \begin{bmatrix}\infty &\infty&\infty &\infty&\infty \end{bmatrix}\times2
\end{align}

In place of $\infty$ we can just put any large number.

After the first step, we have:
\begin{bmatrix}3&3&3&\infty&\infty&6&\cdots&9&\cdots&12&\cdots &15&15&15&\infty&\infty\end{bmatrix}
Second step: \begin{bmatrix}3&6&9&12&15\end{bmatrix}
Finally we get the median-of-medians $9$. However in the initial array only $3\cdot 3\times 3 = 27$ of $5 \cdot (2+3) \cdot 5 = 125$ elements ($21.6\%$) are $\le 9$. Which seems to violate the 30% bound.

I doubt the algorithm is incorrect so what am I getting wrong? A proof would be much appreciated.

You missed the recursive step of this recursive algorithm.

For the sake of discussion, assume you want to find the 99th smallest element of the initial 125 elements. Here 99 is just an arbitrary number between 1 and 125.

After you have got the first batch of medians below,
$$[3\,\,3\,\,3\,\,\infty\,\,\infty,\,\,6\,\,6\,\,6\,\,\infty\,\,\infty,\,\,9\,\,9\,\,9\,\,\infty\,\,\infty,\,\,12\,\,12\,\,12\,\,\infty\,\,\infty,\,\,15\,\,15\,\,15\,\,\infty\,\,\infty]$$
you are supposed to apply the same algorithm to find its median, $m_1$, its actual real median instead of an approximate median.

When you get the second batch of medians, $$\begin{bmatrix}3&6&9&12&15\end{bmatrix}$$
you are supposed to apply the same algorithm to find its median, $m_2$. In fact, we have reached the base case of the recursion. So we just use some simple routine to get its median, $m_2=9$.

Using 9 as the pivot, we will find in the second batch of medians, two elements that are smaller than 9, 3 and 6. Going back to the first batch of medians, we will then skip three 3's and three 6's and two 9's, 3+3+2=8 elements in total. That is where the 30% comes from: $8 \ge 25 * 30\%$. We also find $12\gt9$ and $15\gt9$. Going back to the first batch of medians again, we will skip $[\infty,\infty]$, $[12,\infty,\infty]$ and $[15,\infty,\infty]$, another 8 element in total. That is where the 70% comes from. Now it is time to run the same algorithm again to find the median $m_1$ as the median of the remaining $25-8-8=9$  elements,
$$[\infty\,\,\infty\,\,\infty\,\,\infty\,\,9\,\,12\,\,12\,\,15\,\,15]$$

$\cdots, \cdots, \cdots$ (rounds of recursions omitted)

Finally, we find that $m_1=15$ (the first 15). Using 15 as the pivot, we will find in the first batch of medians, $3<15$, $6<15$, $9<15$ and $12 < 15$. Going back to the initial 125 elements, we will skip three [1,2,3], three [4,5,6], three [7,8,9], three [10,11,12] and one [15, 15], 3*3*4+2=38 elements in total. That is again where the 30% comes from: $38 \ge 125 * 30\%$.  We will apply the same algorithm to find the ultimately wanted element as the $99-38=61$-th smallest element of the remaining $125-38=87$ elements. Why can we skip those 38 elements? Because each of one of them is not greater than $m_1$, which is no greater than the 38 elements on the big side. Together with the fact $38 + 99 \ge 125$, we know the 99-th smallest element must be one of the remaining elements.

Hopefully, I have given enough explanation to show where you have gone wrong. Hopefully, you will appreciate the ingenuity and subtlety of this algorithm of median of medians more.

For more analysis, you may want to check the beautiful visualization page of the algorithm. You may want to read wikipedia. You can also read CLRS, edition 4, section 9.3, "Selection in worst-case linear time" and its accompanying exercises, whose analysis on the pivot and the recurrence relation is more rigorous and comprehensive.


The communication complexity of non-equality I'm familiar with the fooling set technique to obtain lower bounds for communication complexity protocols. The most basic example is the equality function for which the diagonal matrix gives the fooling set of size $2^n$, because each 1-output needs to be in its own monochromatic rectangle. Also, a similar property seems to be true when looking at 0-outputs: If we have a cover of the 0-outputs by a set of monochromatic rectangles, then no rectangle can contain all 0-outputs of 2 (or more) rows. This implies that we get the same complexity for the NEQ (non-equality) problem.

However, I read that for non-deterministic algorithms, the complexity of NEQ is only $O(\log n)$. This is because we simply need to "guess" an index $i$ where the inputs of Alice and Bob differ, which takes $\log n$ bits and then use $1$ additional bit to encode if $i=0$ or $i=1$.

But the complexity of such a non-deterministic algorithms is lower-bounded by the log of the size of the smallest cover of the $0$-outputs, which would still be $\log(2^n)=n$ (by the above argument that each row in the matrix accounts for at least one rectangle in the cover).

Obviously, I'm missing something here, but I haven't figured out what it is...

The protocol gives you a covering of the zeroes using $2n$ rectangles $R_{i,b} = X_{i,b} \times Y_{i,1-b}$, where $X_{i,b}$ (or $Y_{i,b}$) is the set of words whose $i$th bit equals $b$.


Finding the shortest path in a grid which has walls The problem is that you want to travel from the top left corner of a grid to the bottom right corner (You are initially at the top left corner). Now, there are some walls in some cells, and you have a magic wand which you can use $k$ times to destroy a wall. How do we find the shortest path from the top left corner to the bottom right?

Let $w$ be the width of the grid and $h$ be its height. Let $n = w \cdot h$.
The following solution requires $O(n k)$ time and works regardless of whether there are restrictions on the direction of movement. If the movement is allowed only downwards and rightwards then there is a solution with a running time of $O(n)$, which is better whenever $k$ is not a constant (see Nir Shahar's answer).

Assume that there is no wall on the upper-left cell (otherwise remove it, and decrease $k$ by $1$).

Construct a directed graph $G$ as follows: the vertex set $V=\{1,\dots,h\} \times \{1, \dots, w\}$ consists of $n$ nodes. A generic node $(i,j) \in V$ represent the cell in the $i$-th row and $j$-th column of the grid.

There is an edge between vertex $u$ to vertex $v$ iff it is possible to move (in one step) from cell $u$ to cell $v$ without breaking a wall on $v$.
If all directions of movement are allowed this is equivalent to saying that $u$ and $v$ are adjacent and there is no wall on $v$.

Create a directed graph $H$ consisting of $k+1$ copies $G_0, G_1, \dots, G_k$ of $G$.
Intuitively the $i$-th copy represents the situation in which exactly $i$ walls have been broken.

Augment $H$ as follows: for each $i=0, \dots, k-1$ add an edge from vertex $u$ of the $i$-th copy to vertex $v$ of the $(i+1)$-th copy iff it is possible to move (in one step) from cell $u$ to cell $v$ but this requires breaking a wall on $v$.
Again, if all direction of movement are allowed this is equivalent to saying that $u$ and $v$ are adjacent and there is a wall on $v$.

Finally, add a new vertex $t$ and all the edges from vertices $(\ell, \ell)$ in all of the $k+1$ copies of $G$ to $t$.
Notice that the number of vertices is $O(nk)$ and that the number of edges is linear in the number of vertices.

It now suffices to find a shortest path $P = \langle v_0, v_1, \dots, v_h \rangle$ from vertex $(0,0)$ in $G_0$ to $t$.  This can be done in time $O(nk)$ using, e.g., a breadth first search from $(0, 0)$ in $G_0$.
The sought shortest path on the grid has length $h$ and is obtained by traversing the cells corresponding to vertices $v_0$ to $v_{h-1}$.


Worst time complexity for finding a median number for a list and array data structure This was a question that came up in a past exam paper in my computer science course, it states:

"There are two simple, un-optimised sorted data structures, each storing
n numbers. The first is a list; the second is an array. What is the
worst-case complexity of extracting the median number from each data
structure? Are the averages cases different? Why?"

I would like to know the answer to this question as I am confused on what is being asked? Should we not be analyzing algorithms like binary search and not the data structures themselves?

The term "data structure" typically refers to a way to organize/store data, and the operations to create, maintain, and access them.

The asker is probably expecting you to assume specific implementations, probably as given in the course, then come up with algorithms to access the median, and discuss their respective runtime cost.


Are syntax and semantic just 2 structures such that one is a model of the other? The syntax of a language is a structure.
The semantic of a language is a structure.
The semantic of a language is a model of its syntax.

And that's all ? The duality syntax/semantic is just model theory applied to languages ?

(A short answer could be ok; I have already read the wikipedia pages !)

I am afraid the phrasing of the question misled me (though I did know
better) in first seeing model theory as applying to any two arbitrary
mathematical structures, and being the study of homomorphisms of
mathematical structures.

Actually this is wrong. Model Theory already contains the idea of
syntax and semantics, more or less as I define it below. It studies
theories, which are sets of sentences in a formal language, and
models which are interpretation of these sentences in abstract
mathematical structures. This is close to what I call language
below, and I guess this is also close to what the author of the question calls
language.

So the proper answer to the question is that even model theory has a
concept of syntax and semantics, where syntax is a theory, i.e. a
formal representation structure such as a universal algebra, and
semantics is an interpretation (i.e. a morphism) in some abstract
mathematical domain.

Hence the "duality syntax/semantic" is already present in model
theory. There is nothing new on that side.

However, what may make a difference is the understanding of the word
language, as it could be interpreted as going beyond what is usually
concerned by the syntactic algebras usually addressed by model theory.

Actually, the question does not define the word language, and it could
be formal languages, programming languages, natural languages, with
some unsaid understanding of what is intended.

So two possible answers could be:

model theory is the study of languages with their syntax and
semantics, and there is nothing to add, or
a language can be defined by an arbitrary syntactic definition
(meaning a computable structure) and a homomorphic(?) mapping in
some abstract mathematical structure. The question mark is because
I fear that the definition of the mapping may raise some issues.

The second view is possibly less formal, or less constrained. Whatever
the case, I am leaving below my initial answer (which corresponds to
the second view), since several of the issues it is addressing may
still be relevant and of interest to computer scientist, even though
the presentation may be debatable from the point of view of model
theory.

It does not bring anything new from a formal point of view, since the study of formal system that are considered in syntax already had to go all the way to Turing computability, in order to address the Entscheidungsproblem, and that is as far as we may hope to go in terms of syntax.
I may however help understanding some more practical issues.

Your comments are welcome, including suggestions to erase my former, more naive, though possibly more intuitive, answer.

The first section is the direct answer to the question. The other two
sections may be skipped. They are attempts to explore some examples or consequences, or some practical
aspects encountered by computer scientists, in particular in the
design of programming languages.

Syntax, semantics and languages

The view of the issue as expressed in the question is mainly "OK". My
main criticism though is that the reference to the concept of
language is critical, because directly related to the concept of
syntax, not separable from the concept of syntax.

As a consequence, there is something circular, kind of tautological,
about your statement. The question is why do we use this specific
terminology of "syntax and semantics" for some models, for some
homomorphically related pairs of structures, and not for others. Where
is the difference? And a correlated question is: what is a language?

Clearly there is no restriction on semantics: any topic/structure can
be the object/content of a discourse. Hence, the fundamental
distinction is to be looked for on the syntax side. My own
understanding is that what distinguishes such a homomorphic pair is
the domain of the homomorphism: the syntax structure has to be concrete and
concretely manipulatable. Basically a syntactic structure is a
finite collection of concrete objects, usually idealized as symbols,
and a finitely defined collection of rules to compose in diverse ways any unboundedly
finite number of copies of these symbols, and to transform such
compositions into others compositions. The word syntax comes from
'Ancient Greek: σύνταξις "coordination" from σύν syn, "together,"
and τάξις táxis, "an ordering"'.

Fundamentally, syntax is physical. The concept of symbol is only a
mean to abstract away the choice of physical instanciation of the
symbols as objects such as sounds, gestures, glyphs, objects, stones
(which gave us the word calculus), electric or magnetic state,
presence and absence of a signal, etc., or composition of other
symbols.

Hence, the theory of syntax is essentially what is better known as the
theory of computation, which is the study of rule based manipulation
of symbols. Whatever we express, transmit, receive, compute, memorize,
analyze, is processed through some syntactic symbolic representation.

But what we are interested in is not the symbolic representations, but
some semantic concepts or objects (possibly themselves physical) that are
intended to be represented by the symbolic compositions at hand. And
the correspondence is defined by the semantic homomorphism into its
semantic codomain.

Then, in the most general acceptation of the word, a language is the
association of a syntax structure and a semantic structure through a
homomorphic mapping. Or to state it in the terms of the question, it
is a pair of structures such that one is a model of the other, with
the additional requirement that the latter be a syntactic structure.
But, in order to give such a definition, you must first define what
is a syntactic structure. And that definition stands on its own,
independently of the concepts of language or semantics: Syntax
is the study of finitely defined manipulations (including transmission
and memorization) of unboundedly finite compositions of copies of a
finite set of symbols. Ot in simpler terms, syntax concerns the
definition, analysis and manipulation of representations.  You may
read computation theory and information theory.

This is in agreement with the concept of homomorphism: the meaning of
the whole is derived from the meaning of the parts. But this is a
meta-remark. I insist less on defining semantics since it seems that
any structure (that makes sense?) can play that role.

Further remarks

I do not know if the view of linguists on natural language is exactly
the same, or as precise regarding the homomorphic relation, but it
should not be too far from it. The concepts of syntax and semantics
arose from language analysis and logic, which I assume were the same
topic at some point in history (actually diverging pretty late, in the
19th century according to Wikipedia page on syntax). Still, it seems
that some modern linguists follow somewhat similar views "since they regard syntax to be the study of an abstract formal system".

The point is that most mathematical domains, abstract concepts, and
other objects of discourse generally elude us, and can only be
contemplated and dealt with through mechanisms to represent them and
(some of) theirs values, i.e. through syntactic representation. In its
simplest form, it can be a pointing finger to represent a direction.

The main characteristic of a syntactic domain is that it is a concrete
representation, finitely defined through some formal system such as
the formal languages dear to computer scientists. But these syntactic
domains, which are very precisely the domain of computation, i.e. of
syntactic transformations, are very limited, as we learn from the
study of computability. For example, they are denumerable, while many
abstract domains we are interested in are not denumerable.

As a consequence, it is often the case that syntax can only represent
a small part of the mathematical domains we study. This is typically
the case for real numbers, almost all of which do not have a (finite)
syntactic representation, the others being the computable reals.

Choosing a data structure to represent the values of some abstract
domain we wish to compute with is just finding an appropriate syntax,
for your semantic problem, whether to express some conceptual semantic
derivation (computation) or to have simpler relation with semantics (semantic morphism),
or to optimize some aspect of communication and memorization
(space. speed, reliability).

For users who want an example, computing the sum of XXVII and XCII, I
mean 11011 and 1011100, is just a manipulation of the digits to get the
representation of a number (119) that is the sum of the numbers
represented by the initial two representations. The positional
notation happens to be easier to manipulate, to be more economical in
space (number and variety of symbols), and to have a simpler way to
express the homomorphism. The syntax changes, the semantics is the
same, and in both correspond to languages to express natural numbers
(well, not quite for Roman numerals).

IMHO (but some of this may be a matter of individual perspective), if
syntax should be only what can be represented and manipulated,
semantics can be any mathematical domain, or more generally any
abstract domain of discourse, including the domains used for
syntax. Hence you can have a theory of syntax where you study
syntactic representation systems. Formal language theory is nothing
else.

Note that the the idea of a syntac-semantic duality should not
induce the idea that there is some sort of symmetry between syntax and
semantics.

Syntax and semantics in computer science practice

It is true that we often pretend to address semantic issues, for
example when defining formally the semantics of a programming language
$L$. But that may be seen as an abuse. What we really do is use a standard
language $S$ that is supposed to have an accepted semantics and define
the semantics of $L$ in terms of the semantics of $S$. The difficulty
is that we can never access semantics directly, but only through some
syntactic proxy, even when the semantics is itself syntactic in
nature. This is why we use metalanguages such as Backus-Naur Form (BNF).

There are however various mathematical techniques to define semantic
domains. Among these techniques, you have the definition of syntactic
models where the syntax (possibly up to quotient by some equivalence
relation) is its own model. Actually, one of the major contribution of
Dana Scott to computer science was to conceive non-syntactic models of
lambda-calculus which is (initially at least) a purely syntactic theory (see for example
Continuation Models for the Lambda Calculus With Constructors,
B. Petit (2012).

A characteristic of most mathematical theories is that they may have
many models, including non-standard models. "A non-standard model is a
model of a theory that is not isomorphic to the intended model (or
standard model)". That also applies to syntactic theories. Actually,
non-standard interpretation of languages is a very fruitful area of
research in computer science, related to abstract interpretation, type
analysis, flow analysis, partial evaluation and many other approaches
to program analysis.  To take a very trivial, purely syntactic
example, a non-standard interpretation of a program can be a
pretty-printed version of that program. A type checker is usually an
abstract interpretation of the program.

As a consequence, it is clear that the chosen syntax may not capture,
express, all the properties of the intended semantic domain. However,
anything that is considered as syntactically correct must have some
associated semantics through the semantic morphism, even if it is some
special error value. But it is improper, though often done, to state
that the syntax is defined by a context-free grammars, and then
consider programs with undeclared variables as being incorrect. It
cannot be syntactically incorrect for such a reason, because CF
grammars cannot check variable declarations. And I would not know what
it means to be semantically incorrect, other than being possibly a
special error value of the semantic structure.

The dream of programming language designers or implementor is that any
program that can only fail, or that can fail in some specific way,
should be syntactically incorrect. Hence, they have been increasing
the descriptive power of syntax to include as much checking as
possible, limited only by computability constraints. This did lead to
the use of Turing complete formalisms, of which van Wijngaarden's
W-grammars are an example. But this is a pipe dream. Computability
theory tells us that semantic properties of syntactically expressed
functions cannot be checked syntactically, as soon as the language has
Turing power, which we usually expected in programming languages.

In practice, this checking for intrinsic correctness (i.e. independent
of problem specification), or for properties to be used, is often
performed in compilers (or in formal semantic definitions) by what is
called static semantics. Being purely computational, static semantics can be as well considered as part of the syntax.

In the case of programming languages, the semantic domain is a
computation domain.  Given that we allow Turing complete formalisms to
express the syntax, it becomes possible for the syntax to express
completely the semantics. But developing this angle is getting far away
from the original question. Still, this is the main reason why the distinction between syntax and semantics is so difficult to make precise in programming languages.  This may also be the reason why universal Turing machines are possible.

A last point is that defining the semantics as a structure that is a
model of the syntax may not be enough. It could be a model in several
different ways. So it is essential to include the morphism in the
description of the semantics. That is typically what is done with
denotational semantics of programming languages, and a lot of other
formal systems.

Note: This was rather complex and hard to write. If you are to
criticize it, I would appreciate explicit and precise comments. It
would also be useful to other users. Thank you.


Maximum Expected Fishing Day (Recurrence Relation) John joined a meetup where organize day long fishing trip once a
  month. The organizers are vary poor at planning, so will organize
  fishing on a random day of the month without any advance notice.
  Sadly, John needs to inform his boss in order to get time off from
  work at least a day in advance. With this situation, John is forced to
  schedule vacation days and hopping that the fishing will take place on
  them. At the same time, he can be strategic about it. For instance, he
  can wait until the end of the month at which point the fishing would
  have already happened or will guarantee to occur the next day. John
  can use a total of v  day of vacation for the next m months. What is
  the greatest expected number of fishing meetup that he can arrange to
  attend? For simplification, we can assume that a month is only 30 days
  longs.

  It can be approached as: Defining the sub-problems as Maximum Expected
  Fishing Days MEFD: for every situation MEFD(m,d,v), where m is the
  number of months left including the current month, d is the numbers of
  days left in the current one, and v is the number of vacation days
  john left with the assumption that the fishing has not took place in
  the current month.

  Base case: for any (m,d,v) such that i, j or l equals to 0,
  MEFD(m,d,v) =0

  Recurrence Relation: MEFD(m,d,v) = max(MEFD$_{1}$(m,d,v),
  MEFD$_{2}$(m,d,v))

  MEFD$_{1}$(m,d,v)=$\frac{1}{d}$(1+MEFD(m-1,30,v-1))+
  $\frac{d-1}{d}$MEFD(m-1,d-1,v),

  MEFD$_{2}$(m,d,v)=$\frac{1}{d}$(1+MEFD(m,30,v-1))+
  $\frac{d-1}{d}$MEFD(m,d-1,v).

What does $\frac{1}{d}$ or $\frac{d-1}{d}$ means? Why do we need to multiply them ? Let's MEFD$_{1}$ means that the Maximum Expected Fishing Day that John takes a vacation day off in the next day. then it would fall into two cases: 1, fishing meetup take place, 2, it didn't take place.
As we can tell from MEFD$_{1}$,  1 + ing means fishing meetup take place, then we - 1 from the months left and - 1 from vacations left.

What do we also need to -1 from months and vacations of the second part of the equation, + $\frac{d-1}{d}$MEFD(m-1,d-1,v)?

Or am i am reading this recurrence relation completely wrong? any points are really appreciated.

Although the subproblems are defined correctly in the approach quoted in the question, there are some typos and glitches when it comes to the base cases and recurrence relations.

Please see the corrected base cases and recurrence relations below.

Base case: for any $(m,d,v)$ such that $m$, $d$ or $v$ equals to 0,
$$\text{MEFD}(m,d,v) =0\tag{R0}$$

Recurrence Relations:
$$\begin{align*}
\text{MEFD}(m,d,v) &= \max(\text{MEFD}_{1}(m,d,v),  \text{MEFD}_{2}(m,d,v))\tag{R1}\\
\text{MEFD}_{1}(m,d,v)&=\frac{1}{d}(1+\text{MEFD}(m-1,30,v-1))\\&+\frac{d-1}{d}\text{MEFD}(m,d-1,v-1)\tag{R2}\\
\text{MEFD}_{2}(m,d,v)&=\frac{1}{d}\text{MEFD}(m-1,30,v))\\&+\frac{d-1}{d}\text{MEFD}(m,d-1,v)\tag{R3}
\end{align*}$$

Equation (R1) says that the maximum expected fishing days is the larger of the expected fishing days yielded by two strategies, John selects the next day and John does not select the next day. John will proceed with the best strategy in the remaining days.

Equation (R2) compute the maximum expected finishing days when John has selected the next day. The probability that the next day will be a fishing day is $\frac1d$, in which case John will proceed with the best strategy for the remaining $m-1$ months and $v-1$ vacations day. The probability that the next day will not be a fishing day is $\frac{d-1}d$, in which case John will proceed with the best strategy for the remaining $d-1$ day and $v-1$ vacation days.

Equation (R3) compute the maximum expected finishing days when John has decided to work for the next day. The probability that the next day will be a fishing day is $\frac1d$, in which case John will proceed with the best strategy for the remaining $m-1$ months and $v$ vacations day. The probability that the next day will not be a fishing day is $\frac{d-1}d$, in which case John will proceed with the best strategy for the remaining $d-1$ day and $v$ vacation days.

Note "John needs to inform his boss in order to get time off from work at least a day in advance" is interpreted as something like if John wants to take tomorrow off, he can just inform his boss tonight, at which time he must have known whether today is a fishing day. If it is, he will not, of course, select any remaining day in the current month as a vacation day. That is why whenever the next day will be a fishing day, we will only consider the remaining $m-1$ months in the above recurrence relations.


Find an MST in a graph with edge weights from {1,2} I've been asked the following question:

  Given a connected undirected graph $G=(V,E)$ and a weight function $w: E \to \{1,2\}$, suggest an efficient algorithm that finds an MST of the graph.

After a few clarifications, the algorithm should run in time $O(|V|+|E|)$. I believe we can do this because of the fact that there are two types of weight of edges.

I tried the following idea, which did not work (I had a contradicting example):

  Run BFS on the graph, and output the BFS tree.

I thought that shortest paths in this case would also mean easiest trees, but this is not the case.

I also tried to make each edge $e$ such that $w(e)=2$ into two edges of weight $1$ but my friend also gave a contradicting example.

Can you help please? This is not a homework question, this is a previous exam question as I am studying for my algorithms exam which is soon.

Alternatively use Prim's algorithm. No need to keep track of components. Prim considers each edge once (assuming adjacency-lists). The most costly part of Prim is looking for the next vertex to add: the one of the remaining vertices that has the cheapest connection to the tree already constructed. Here we only have to know whether there are still vertices that have a connection of weight 1 (because they have priority to those of weight 2). I would say that a single list can handle this.

I also think that there might be another approach. Start building spanning trees for the components when we only use edges of weight 1, just ignoring edges of weight 2. Then the components are "big vertices" that can be connected by a tree using the remaining edges of weight 2. Keeping components here is easy: all vertices reached in a new component are labelled with the same number. That number identifies the "big vertex".


Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time? According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot \lg(N))$ except for the recursion step which ends up costing $O(N\cdot \lg(N) \cdot \lg(\lg(N)))$.

I don't understand why the same inductive argument used to show the cost of the recursive step doesn't work for $O(N\cdot \lg(N))$.

Assume that, for all $X < N$, the time $F(X)$ is less than $c \cdot X \cdot \lg(X)$ for some $c$.
So the recursive step costs $d \cdot \sqrt{N} F(\sqrt{N})$, and we know this is less than $d \cdot \sqrt{N} c \cdot \sqrt{N} \lg(\sqrt{N}) = \frac{c \cdot d}{2} \cdot N \cdot \lg(N)$ by the inductive hypothesis.
If we can show that $d < 2$, then we're done because we've satisfied the inductive step.
I'm pretty sure recursion overhead is negligible, so $d \approx 1$ and we have $\frac{c}{2} N \cdot \lg(N)$ left to do the rest. Easy: everything else is $O(N \cdot \lg(N))$ so we can pick a $c$ big enough for it to fit in our remaining time.

Basically, without digging into the details that will contradict this somehow, it looks like things would work out if we assumed the algorithm costs $O(N \cdot \log(N))$. The same thing seems to happen if I expand the recursive invocations then sum it all up... so where is the penalty coming from?

My best guess is that it has to do with the $\lg(\lg(N))$ levels of recursion, since that's how many times you must apply a square root to get to a constant size. But how do we know each recursive pass is not getting cheaper, like in quickselect?

For example, if we group our $N$ initial items into words of size $O(\lg(N))$, meaning we have $O(N/\lg(N))$ items of size $O(\lg(N))$ to multiply when recursing, shouldn't that only take $O(N/\lg(N) \cdot \lg(N) \cdot \lg(\lg(N)) \cdot \lg(\lg(\lg(N)))) = O(N \cdot \lg(\lg(N)) \cdot \lg(\lg(\lg(N))))$ time to do. Not only is that well within the $N \cdot \lg(N)$ limit, it worked even though I used the larger $N\cdot \lg(N)\cdot \lg(\lg(N))$ cost for the recursive steps (for "I probably made a mistake" values of "worked").

My second guess is that there's some blowup at each level that I'm not accounting for. There are constraints on the sizes of things that might work together to slow down how quickly things get smaller, or to multiply how many multiplications have to be done.

Here's the recursive expansion.

Assume we get $N$ bits and split them into $\sqrt{N}$ groups of size $\sqrt{N}$. Everything except the recursion costs $O(N \lg N)$. The recursive multiplications can be done with $3 \cdot \sqrt{N}$ bits. So we get the relationship:

$M(N) = N \cdot \lg(N) + \sqrt{N} \cdot M(3 \cdot \sqrt{N})$

Expanding once:

$M(N) = N \cdot \lg(N) + \sqrt{N} \cdot (3 \cdot \sqrt{N} \cdot lg(3 \cdot \sqrt{N}) + \sqrt{3 \cdot \sqrt{N}} \cdot M(3 \cdot \sqrt{3 \cdot \sqrt{N}})$

Simplifying:

$M(N) = N \cdot \lg(N) + 3 \cdot N \cdot lg(3 \cdot \sqrt{N}) + \cdot \sqrt{3} \cdot N^{2-\frac{1}{2}} \cdot M(3^{2-\frac{1}{2}} \cdot \sqrt{\sqrt{N}})$

See the pattern? Each term will end up in the form $3^{2-2^{-i}} \cdot N \cdot lg(N^{2^{-i}} 3^{2-2^{-i}})$. So the overall sum is:

$\sum_{i=0}^{\lg(\lg(N))} 3^{2-2^{-i}} \cdot N \cdot \lg(N^{2^{-i}} 3^{2-2^{-i}})$

We can upper bound this by increasing the powers of 3 to just 3^2, since that can only increase the value in both cases:

$\sum_{i=0}^{\lg(\lg(N))} 9 \cdot N \cdot \lg(N^{2^{-i}} 9)$

Which is asymptotically the same as:

$\sum_{i=0}^{\lg(\lg(N))} N \cdot \lg(N^{2^{-i}})$

Moving the power out of the logarithm:

$\sum_{i=0}^{\lg(\lg(N))} N \cdot \lg(N) \cdot 2^{-i}$

Moving variables not dependent on $i$ out:

$N \cdot \lg(N) \sum_{i=0}^{\lg(\lg(N))} 2^{-i}$

The series is upper bounded by 2, so we're upper bounded by:

$N \cdot \lg(N)$

Not sure where the $\lg(\lg(N))$ went. All the twiddly factors and offsets (because many recurrence relations "solutions" are broken by those) I throw in seem to get killed off by the $\lg$ creating that exponentially decreasing term, or they end up not multiplied by $N$ and are asymptotically insignificant.

The sticking point is the size of the integers in the recursive step, which is not quite $\sqrt{n}$, but rather twice as large, since the product of two $t$-bit integers has size $2t$. Assuming that we break the original $n$-bit integer into $\sqrt{n}$ parts of length $\sqrt{n}$, the running time recursion is
$$ T(n) = n\log n + \sqrt{n}T(2\sqrt{n}), $$
and by expanding it, we get
$$
\begin{align*}
T(n) &= n\log n + \sqrt{n}T(2\sqrt{n}) \\ &=
n\log n + 2n\log (2\sqrt{n}) + 2^{1/2} n^{3/4} T(2^{3/2}n^{1/4}) \\ &=
n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^{5/4} n^{7/8} T(2^{7/4} n^{1/8}) \\ &=
n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^3 n \log (2^{7/4} n^{1/8}) + \cdots,
\end{align*}
$$
so each level of the recursion takes time proportional to $n\log n$. Since there are $\log\log n$ levels, we get the quoted running time. For more information, check out these lecture notes.