Derivative for x-direction for image I want to ask, consider we want to compute the slope of x-direction of the following step

.

The slope for it would be

$m =\frac{0}{m_2 - m_1} =\frac{0}{5 - 2}$ which is 0.

But the derivate for image in x-direction computed with (something like, some symbols aren't existed in my phone so lets just say $\frac{df}{dx}$)

$\frac{df}{dx} = f(x+1) - f(x)$

It's computed under the consideration of next pixel $f(x+1)$ minus current pixel $f(x)$.

Is there any interpretation that I'm missing, shouldn't it be 0, in both cases?

From my understanding, you are asking about computing the derivative, at some pixel $(x,y)$, with respect to the $x$ direction. We can approximate a derivative of some function $f(x,y)$ along the $x$ direction using the following Finite Difference formula:

$$ \frac{\partial f}{\partial x} \approx \frac{f(x+h,y) - f(x,y)}{h} $$

for some $h \neq 0$, usually using $h \ll 1$ if possible. For an image, the best you can do with this formula is the following:

$$ \frac{\partial f}{\partial x} \approx \frac{f(x+1,y) - f(x,y)}{1} = f(x+1,y) - f(x,y) $$

This is because $f(x,y)$, the pixel color values at $(x,y)$, is a value of $1$ away from the nearest neighboring pixels in both the $x$ and $y$ direction.


Logarithmic guarantees for randomized search trees In this paper [1], "treaps" and "randomized search trees" are introduced. The idea is to guarantee logarithmic update and query operations by assigning uniform random priorities to the keys being inserted into the tree.

The authors assume that randomness is "hidden" from the user:

  All expectations are with respect to randomness that is "controlled" by the update algorithms. For the time being we assume that the priorities are kept hidden from the "user." This is necessary to ensure that a randomized search tree is transformed into a randomized search tree by any update. If the user knew the actual priorities it would a simple matter to create a very "non-random" and unbalanced tree by a polynomial number of updates.

I don't actually understand what is meant by that. Specifically, I don't understand what the user might be able to do to affect the runtime by observing the generated priorities. My ideas of trying to understand that are:

The user might be able to provide keys in certain order to make the resulting trees unblanaced! However, I don't think this is right because the priorities are not generated based on key values.
I understood the paragraph wrongly and they actually mean that the priority generation is controlled by the user not just seen by the user.

[1] https://faculty.washington.edu/aragon/pubs/rst96.pdf

Let's consider a different example: a hash table. While usually the hash function is fixed in advance, it is also possible for it to be chosen randomly when the hash table is initialized.

If we want to mount a Denial of Service attack on a hash table, we need to feed it many keys that hash to the same value. If the hash function is weak and known, then we can easily do it. If the hash function is weak and unknown, then it could be difficult or even impossible.

When the authors say that the priorities are kept hidden from the user, they mean that the randomness used in the data structure is not "public". In our hash table example, it means that the user of the hash table doesn't know which hash function was chosen. If the user knew the hash function then she could mount a DoS attack. If she doesn't, then such an attack becomes much more difficult.

In practice we don't necessarily think of the user as malicious; however, we want a guarantee on the running time which is independent of how the data structure is used. Suppose that we use a treap or a randomized BST in some algorithm, in a very specific way. If the algorithm has access to the randomness—for example, if it is fixed—then perhaps its specific access pattern results in bad performance. However, if the algorithm acts independently of the randomness, then bad performance only happens with small probability.


Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum I have found an algorithm that runs quite fast on Subset Sum problem few years ago (sometime around 2016). It basically sorts the input set in descending order (instead of the regular ascending) and does the backtracking then to arrive at results. It solves a 1,000,000 instance set in 5 minutes on my i5 8 GB RAM machine!

This year I stumbled upon this github repo:
GitHub Link for Subset Sum
by another user, who claims to have solved it in amortized O(n) complexity as per his detailed analysis available on the repo. Does this prove P=NP as well, as maybe amortized O(n) implies polynomial complexity for the problem?

P.S. that I have come across many fast Subset Sum problems but I am just curious in this specific case as it relates to my algorithm too.

This is not what amortized analysis means: you can not infer the worst case runtime of an algorithm by plotting the actual execution time on larger and larger instances of some specific structure. Sadly, that doesn't prove you have a polynomial-time algorithm. Even when you want to do experimental work, there are other parameters to vary besides the size of the input that will have a major impact on the runtime of the proposed solution. If you do so, you will have a result that roughly says "here's an algorithm that performs well in practice for instances that look like this, but I can't give any theoretical guarantees".
To summarize, it's not impressive to have an algorithm which solves huge instances belonging to a specific family of instances of an NP-hard problem quickly. What is impressive (or rather extremely remarkable), is to have an algorithm that you can prove runs in time that is polynomial in the size of the input regardless of the structure of the instance.


How to balance the inflow and outflow of each vertex in a bipartite graph? I have a situation where in a group of people, every person is trading with multiple people and giving them some money. It can be visualised as a directed bipartite graph with L and R as the total set of people. A directed edge from l to r means l gave r some money with weight w which is the weight of the edge. Now I'm an auditing firm and want to make sure that the total amount given out by a person should be as close as possible to the amount received by him. I can limit each such transaction (implying I can reduce the weight of any edge in the graph). What is the best way to solve this approximately with the minimum restrictions required (in terms of actual amount)?

Ex. if

a -> 10 -> b
b -> 10 -> c
c -> 5  -> a

can be limited to

a -> 5 -> b
b -> 5 -> c
c -> 5 -> a

by reducing 10 units of transactions

You can write a linear program. For each edge you have a restriction variable. You want to minimize the sum of the restriction variables. For constraints you want to have the sums of the differences between outgoing edges and the incoming edges (minus their restriction variables) to be smaller than a threshold that you choose.


Proofs based on narrowing down sets of possibilities Consider the argument made in this question based on the comparison sorting lower-bounds proof, which runs as follows.

First, the comparison sorting lower-bounds proof was recited:

For $n$ distinct numbers, there are $n!$ possible orderings.
There is only one correct sorted sequence of the $n$ numbers.
We are given that comparison ($<$) is the only operation we have that can narrow down the $n!$ possible orderings, and each comparison has only two possible outcomes.
So $\log_2(n!)$ comparisons are required.

Then, the argument was generalized:

Define a space of input possibilities
Define the goal space, a subset of the input space
Define the amount of information that is gained at each step of the computation
Calculate the information difference between the space of possibilities and the goal space and divide by the information gain per step to yield the lower bound on the number of steps.

Both arguments above rely on information arguments to prove a lower bound on the number of steps.

Question: are there proofs and/or proof strategies like the above which:

prove lower bounds,
define an input space,
define a goal space which is a subset of the input space, and
do not rely on information arguments?

The more general argument is an example of an adversary argument. A nice example is a lower bound for the number of comparisons needed to find the minimum and the maximum at the same time. Said number is $\lceil 1.5 n \rceil - 2$. You can try to construct the algorithm and prove its optimality, or just have a look at the paper.


Is this an example of a type-0 grammar that is not context-sensitive? A type-0 grammar generates a recursively enumerable (RE) language.

A RE language is also known as a semi-decidable language.

A semi-decidable language is a particular kind of undecidable language: If a language is semi-decidable, we can write a method that returns true for each string that is an element of the language; for strings that are not an element of the language, the method may return false or it may loop indefinitely.

Problem: Provide an example of a type-0 grammar which generates a language that is not context-sensitive (i.e., not decidable).

Answer (I think): The following grammar generates this language:

(a+b+) union (infinite a's)

Here is the grammar:

S → aA | bE
A → aA | bB
B → bB | ε | aE
bE → aE
E → aE

A method for recognizing strings in the language generated by this grammar would return true for strings that are an element of a+b+ and would run indefinitely for strings that are not an element of a+b+

I think that this is an example of a type-0 grammar which generates a language that is not context-sensitive (i.e., not decidable).

If I am incorrect, would you provide an example please?

The language you state in the question, $L=\{ a^+b^+\} \cup \{a^* \}$ is is regular (even though expressed via a context-sensitive grammar) and thus it is not undecidable.

To generate an undecidable language, you can think of a Turing machine for that language, and try to simulate the behaviour of the TM by the grammar. For instance, the nonterminals can be the TM's state (and their position in the sentinel clause will be the head's position). Now a move of the head can be described by grammar transitions of the form $aQb \to Qab$ or $aQb \to abQ$, etc.


Fastest known algorithm for $3$-$\mathrm{Partition}$ problem $3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known exact algorithm that solves $3$-$\mathrm{Partition}$.

Is there a fast (e.g subexponential) algorithm for $3$-$\mathrm{Partition}$? Is it possible to solve it faster than using SAT solvers?

If you find a fast (sub-exponential) exact algorithm for 3-Partition , while 3-Partition is NP-Complete, then dear sir you have just proven P=NP, which no body has done so far, and you have a 1M $ price waiting for you as well as wealth and fame, cheers.

Anyway if you do have a faster than a SAT solver, wouldn't you actually be performing SAT it's self faster? I mean if you can reduce SAT to 3-PARTITION and you can solve 3-PARTITION in sub-expo time, doesn't that mean that SAT can be solved in sub-expo time, hence all NP-COMPLETE problems also can be solved in such time? So you might as well be looking for a sub-expo time solution of any other NP-COMPLETE problem just as well, it would still be a significant breakthrough.


Busy-Beaver-like question for WHILE-Programs (Theoretical CS) So this is exam-task is called "Busy WHILE-Programs"

In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:

Variables             x1,x2,...  (initially all 0 and can only be positive)
Constants c           0,1,2,3,...
Assignment            xi := c
Addition/Subtraction  xi := xj + c, xi := xj - c
while-loops           while(xi != 0) { ... }

In part (a) of the task we should show, that every WHILE-program can be simulated by a WHILE42-program.

A WHILE42-program is a WHILE-program where all constants can only be 42 or lower.

Now the task where I need help (I try to translate from german):

Let WHILE42(n) be the subset of all WHILE42-programs, with no more than n instructions/commands. The function g(n) returns the biggest value, a terminating program from the WHILE42(n)-subset assigns any of it's variables. Prove or disprove the following statement:

The function g(n) is not computable

I have two routes with the second being probably a valid answer:

First: My intuition tells me it is not computable and that I should show (like in the Busy-Beaver-example) that if it would be computable, it would solve the Halting-problem. Which would show, that it can't be computable.

My thought-process so far:

If g(n) is computable, I could take any TM M_1 and transform it in a WHILE42-program W_1 with n_1 commands.
I could then calculate g(n_1).

Then I need to show that from this value g(n_1) I can derive somehow an upper value of how many steps I need to simulate M_1 to decide if it will terminate or run forever.

But I struggle to determine what this upper value is.

Second: Here my intuition tells me, that this is not how it is expected to be solved. So I would prefer a solution to the first one, if there is any

If g(n) is computable, there is a TM M_g that calculates g(n). M_g could be transformed in a WHILE42-program W_g with n_g commands.

Since W_g would for any n at some point assign the highest value for this WHILE42(n)-subset, g(n_g) can not compute a value. For any value k  g(n_g) could return, it would be possible to construct a terminating WHILE42-Programm that adds the value 42 k-times to a variable which would grow larger than k.

Use the same proof as Radó did in his paper: Assume there is a program $\Sigma$ that computes the value asked for, combine with a program that given $n$ computes $2 n$, and add $1$ to the result. Call the number of lines of the result $N$. Writing a program that computes $N$ should take at most $N$ lines (add $1$ $N$ times). Combine the above, the result is of length $2 N$ and computes a value larger than the largest it is able to compute given it's length. Contradiction, $\Sigma$ can't exist.


Proving a set is at a certain level of the arithmetical hierarchy I'm interested in methods for proving a set is at some level $\Sigma^0_n$ (or $\Pi^0_n$) in the arithmetical hierarchy, and in particular, proving it is at the level with the smallest $n$ possible.

I know that a set is in $\Sigma_n^0$ if it can be expressed as a sequence of $n$ quantifiers (starting with $\exists$ and then switching between $\exists$ and $\forall$) on variables, followed by a decidable formula on those variables. I also know membership in $\Pi_n^0$ can be proved in a similar way, just starting with $\forall$ instead of $\exists$.

These slides use that approach to place several sets at different places in the arithmetic heirarchy (on slides 26,31,33, and 35, for example).

Here's where things start to get tricky for me. If a language is in $\Sigma^0_n$, it seems like it's also trivially in  $\Sigma^0_{n+1}$,  $\Sigma^0_{n+2}$, and so on -- because you can take the formula you used to show that the language was in $\Sigma^0_n$, and tack on "dummy" quantifiers that don't actually do anything.

So, let's say I want to proving that a language is in $\Sigma^0_n$, but not $\Sigma^0_{n-1}$, i.e. I want to put the language in its lowest spot on the arithmetical heirarchy. Now, it seems like just showing that the language corresponds to a  a $\exists,\forall,...$ sequence followed by a decidable formula won't cut it, because there's a chance that I was adding useless quantifiers to artificially inflate my language's difficulty. What techniques exist to get around this issue -- How do I prove that my quantifiers are "essential", so to speak?

I'm definitely interested in being as formal as possible with such a proof, so any links to textbooks or papers would be much appreciated.

In order to show that a language is in (say) $\Sigma_n^0$ but not in $\Sigma_{n-1}^0$ or $\Pi_{n-1}^0$, we show that the language is complete for $\Sigma_n^0$. Since the arithmetical hierarchy is strict (by a generalization of the proof of the uncomputability of the halting problem by diagonalization, which you can find in many different sources), a $\Sigma_n^0$-complete language cannot be in any lower level of the hierarchy.

How do we show that a language is complete for a level of the hierarchy? Either by a direct proof or by reduction. Let me illustrate both techniques using variants of the halting problem.

We will consider two variants of the halting problem:

$H_1$ consists of all pairs $(\langle M \rangle, x)$ such that $M$ is a Turing machine halting on $x$.
$H_2$ consists of all singletons $\langle M \rangle$ such that $M$ is a Turing machine halting on an empty tape.

Let us show that $H_1$ is $\Sigma_1^0$-complete by a direct proof. In order to show that it is in $\Sigma_1^0$, we notice that $(\langle M \rangle,x)$ iff there exists $t$ such that $M$ halts on $x$ within $t$ steps; the latter predicate is computable.

In order to show that $H_1$ is $\Sigma_1^0$-hard, consider any language $L \in \Sigma_1^0$. By definition, there exists a computable predicate $P$ such that
$$ x \in L \Longleftrightarrow \exists y \, P(x,y). $$
Let $M$ be a Turing machine that on input $x$, enumerates all strings $y$ (say first by length, then lexicographically), for each one computes $P(x,y)$, and halts if $P(x,y)$ holds for any $y$. Then $x \in L$ iff $(\langle M \rangle, x) \in H_1$. The mapping $x \mapsto (\langle M \rangle, x)$ is clearly computable, and so this reduces $L$ to $H_1$.

We now show that $H_2$ is $\Sigma_1^0$-complete by reduction from $H_1$. Given an instance $(\langle M \rangle, x)$, we construct (in a computable way) a new machine $M_x$ that first initializes the tape $x$, and then transfers control to $M$. Clearly $(\langle M \rangle, x) \in H_1$ iff $\langle M_x \rangle \in H_2$. Since the reduction is computable and $H_1$ is $\Sigma_1^0$-hard, this shows that $H_2$ is also $\Sigma_1^0$-hard. Also, $H_2 \in \Sigma_1^0$, using the same proof as above. So $H_2$ is $\Sigma_1^0$-complete.


What makes a nested function in gcc so complicated? Disclaimer: I'm not a compiler expert, but some of my best friends are!  :)

I do a lot of embedded systems programming where stack (and other memory) is limited.  Most of my code is written in gcc, so I thought nested functions could be useful for reducing stack usage.  Here's an example of what I had in mind:

(Though the algorithm isn't important for this question, assume that list_traverse takes a pointer to a list head and a function.  The contains_aux() function gets called with each element in turn.)

bool list_contains(list_t *head, list_t *item) {
  bool found = false;
  void contains_aux(list_t *list) {
    if (list == item) {
      found = true;
    }
  }
  list_traverse(head, contains_aux);
  return found;
}

I assumed that the nested contains_aux() function would be able to directly reference its lexically closed variables (found and item).  But I was wrong.

Instead, looking at the generated code, I see that it installs some sort of trampoline function on the stack and calls that before getting to the contains_aux() function.

I know that contains_aux() can't share the same stack frame as list_contains() because there's an intervening function on the stack (list_traverse()), but -- geez -- it seems like the compiler could pass the frame pointer from list_contains() so contains_aux() could access its locals.

Is there a reason it doesn't work this way?  Is there a way I could torture the compiler into doing that?  Or should I just resign myself using un-nested functions and passing a "context" object to contains_aux()?

I don't see any obvious reason why the compiler could not inline the call to list_traverse, assuming that it is a simple and that its definition is available in the translation unit. But apparently it doesn't. (Actually, I do see an obvious reason: "It would be a lot of work, and the benefit might not be great." Not saying that that statement is necessarily valid, but a reason can be just a suspicion.)

Without inlining, though, it's very difficult to see how the trampoline could be avoided. The frame containing the variables has to be passed through list_traverse so that it can be handed off to contains_aux. But presumably list_traverse is used elsewhere, and those other calls might not even involve a nested function, in which case there would be no stack frame to be passed through. There's nothing in list_traverse's prototype which specifies that it might be called with a nested function, so if it has external linkage, it needs to be usable with the standard calling convention, which has no room for hidden parameters. And if it is called with a nested function, there is no guarantee that the nested function it is called with was nested in the same way. (For example, there might be more than one stack frame which needs to accompany the closure, if the bound variables come from different places in the call stack.)

So aside from inlining, the only safe solution is to manufacture something which can be called like an ordinary function, thereby conforming with the type of list_traverse's first argument.

As evidence that inlining is possible, I offer the following C++ program, in which the same compiler happily inlines the lambda:

struct list_t {
    int value;
    list_t* next;
};

template<typename F>
void list_traverse(list_t* head, F check) {
    while (head && check(head))
        head = head->next;
}

bool list_contains(list_t *head, list_t* item) {
    bool found = false;
    list_traverse(head, [&](list_t *list)->auto {
        return list == item ? (found = true, false) : true;
        });
    return found;
}

(Alternatively, with a strangely bloated result: https://gcc.godbolt.org/z/s9XqW7).

I do understand that inlining might not be exactly what you're looking for, though.


Applying Master Theorem to: T(n) = T(n - 2) + n^2 I've been learning master theorem in school now and have learnt how to apply it to a number of recurrence relations. However one of my assignments has the following recurrence relation:

T(n) = T(n-2) + n^2

Am I wrong in thinking that I cannot apply Master Theorem to this equation? If it can be applied, I am unsure how, as the variable T(n-2) gives no value for "b" which would usually be used to solve with master theorem.

If it can be solved with Master Theorem, how would it be solved? If it cannot be, how would one go about solving this specific recurrence relation?

Thank you in advance for any help and clarification!

Think about what the derivative of T is. If the difference between T (n) and T (n-2) is $n^2$ then the derivative T' (n) is about $n^2 / 2$ and T (n) is about $2/3 · n^3$.


Why frame must be longer than generator polynomial? Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 213:

  When the polynomial code method is employed, the sender and receiver must agree upon a generator polynomial, $G(x)$, in advance. Both the high- and low-order bits of the generator must be $1$. To compute the CRC for some frame with $m$ bits corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial. The idea is to append a CRC to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by $G(x)$. When the receiver gets the checksummed frame, it tries dividing it by $G(x)$. If there is a remainder, there has been a transmission error.

My question is why to compute the CRC for some frame with $m$ bit corresponding to the polynomial $M(x)$, the frame must be longer than the generator polynomial?

I tried to search for the reason but couldn't really find the exact answer, so in my opinion, if the generator polynomial is longer than the frame, it will create check bit that is more than data bit which is redundant because CRC is used in error detecting code and error detecting code is used in places where fewer error occur. But is that true?

If the CRC polynomial is $m$-bit long, then in order to create $M'$ from $M$, you need to add $m$ bits (or perhaps $m-1$ bits). In particular, the final message $M'$ is at least $m$-bit long.


DNA Computing Algorithm to solve the Hamiltonian problem Is it possible to represent the algorithm proposed by Adleman to solve the Hamiltonian problem in a probabilistic Turing Machine?

See also Computing with DNA

Yes, of course.  The Hamiltonian path problem is decidable, so it can be solved using a Turing machine.

I recommend you read about the Church-Turing hypothesis, decidability, and undecidability.  I think you'll find those topics of interest.


What is the complexity of Array[n] and Object.value I faced a great doubt about the Complexity of two ways of calling a information.

First I have an Array, if I call an array in a program like this:

print array[0]

This process will be O(1) as I understand.

But what is the complexity of something like this:

class Obj:
    value = 1
print Obj.value

Is this complexity is the same of callin and array by Index? If we ignore the process to create the object.

If you have CPython in mind then yes, the both are $O(1)$.
To get array by index the address is calculated as pointer to first element + index * size of element, and for object, which uses struct it is pointer to struct + offset, where offset is calculated at compilation.

The general runtime of operations depends solely on data structure used internally by given implementation of language (please note that language itself might not indicate what structure must be used and the very same language might have different structures using different vendors). It may be offset table, hash table, balanced tree etc.


When are 2 decision/optimization problems equivalent? Does anybody know a good definition of 2 decision / optimization problems being equivalent?

I am asking since for example allowing polynomial time computations any 2 problems in NP could be considered equivalent.

Suppose $L_1$ and $L_2$ are two decision problems, and $\mathcal{A}$ is a class of algorithms (like $P$). Say that $L_1$ is $\mathcal{A}$-reducible to $L_2$ if there is an $f \in \mathcal{A}$ such that $x \in L_1$ iff $f(x) \in L_2$. Say that $L_1$ and $L_2$ are $\mathcal{A}$-equivalent if each is $\mathcal{A}$-reducible to the other. For example, all NP-complete problems are $P$-equivalent. If you want a finer notion, you can consider more restricted classes, such as log-space or even AC0. Such notions of reducibility actually come up in refinements of Schaefer's dichotomy theorem.

As for optimization problems, let's consider maximization problems. With each maximization problem $L$ (which is a function mapping instances to optimal values), you can associate the decision problem $L'$ consisting of pairs $(x,v)$ such that $L(x) \geq v$. Now you can define reducibility and equivalence as before.


Given max-flow determine if edge is in a min-cut We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or not e belongs to a min-cut.

From the grading rubric we are told a correct algorithm - I got dinged for not having the correct algorithm according to the rubric. I have flushed out my algorithm and can’t see why it is wrong. There are similar posts, but they all solve problem by running max-flow after adjusting e downwards, which is at best a polynomial algorithm O(mn) Orlin+KTR, and at worst pseudo-polynomial O(Cm) Ford-Fulkerson.

Here is rough description:

Since have max flow, create residual graph Gf. O(m)
Find the first min-cut by the normal method of BFS search for all nodes reachable by S in Gf. Check if edge e is in this cut. If it is in min-cut we are done.
Since it was not in the min-cut, look for the next min-cut if there is one. Do this by modifying Gf by removing the nodes in the min-cut set and adding a forward edge from a new S to the nodes on the other side of the min-cut. That way the edges from the new S to the existing nodes on the other side of the min-cut will not be part of any min-cut.
We then repeat 2 using this new graph which will find the next min cut.
We stop when we can get to t, which at this point if edge not found then it is not in min-cut

Since we traverse the tree only once this is generally O(m), although in the modifications to Gf we may have to traverse a node twice (think a straight line graph with every edge being a minimum cut) so it is worst case O(m + 2m) -> O(m)

Update:

After researching more (Does Ford-Fulkerson always produce the left-most min-cut), refining my claim that the above algorithm will find every edge e that is part of a min-cut (not every minimum cut which is exponential).

Looking at my example below, you will see that there are 4x4x4x4 = 256 minimum cuts in the graph, but only 4+4+4+4 = 16 edges that appear in a minimum cut.

Proof:

Let’s say that this algorithm misses an edge that is in a minimum cut. If this is the case, when we did a BFS in the residual graph we were able to traverse through that edge. But the only way BFS can traverse that edge would be if it has forward capacity, but since this is an edge in a minimum cut this is not possible, a contradiction. If we can reach the node on the other side of that edge during our BFS that also means that this edge can’t be part of a min-cut, which the algorithm would figure out.

Will not find A-E, B-C min-cut. Will find A-B, A-E and C-D. Graph does not show flow direction, but assume left to right (i.e. A->B, B->C, A->E, E->C and C->D)

    B
   / \
1 /   \ 1
 /     \   2
A       C --- D
 \     /
1 \   / 4
   \ /
    E


How to prove the following properties of Small-step semantics? I have to prove the following 2 properties of the Small-step semantics of the WHILE programming language:

If $\langle C_1; C_2, s\rangle \rightarrow^k s'$ then there is a
state $s''$ and natural numbers $k_1$ and $k_2$ such that $\langle C_1;s
   \rangle \rightarrow^{k_1} s''$ and $\langle C_2; s'' \rangle
   \rightarrow^{k_2} s'$ where $k_1 + k_2 = k$.
If $\langle C_1, s \rangle \rightarrow^k s'$ then $\langle C_1; C_2,
   s \rangle \rightarrow^k \langle C_2, s'\rangle$.

I am not quite sure which kind of induction I should use. I am not asking for a full proof, I would rather appreciate some hints on which kind of induction I should use in this case. Thanks in advance!

I suggest to proceed by induction on $k$. For the inductive basis and step you'll have to look at all the possible cases that the relevant reduction step $\langle C, s \rangle$ can be derived.


regular expression given the language The language is:
$$
L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \}
$$

My attempt at an answer:
$$
(a \cup b)^{3k}
$$

This will work if the a OR b can change for each instance in the string that is (3k) long. If not, what can I do to fix this?

First off, putting $k$ in the regular expression is not allowed by typical regular expression syntax, unless I'm mistaken. Even adding constant powers is a shorthand notation, not a part of the regular expression formalism. Even if it were possible, using that notation, you could mix $a$s with $b$s, so that not all $a$'s would necessarily come before all $b$s ... so that's not the right direction.

You want strings that begin with $a$s, end with $b$s, and have a total length that is divisible by three. There are a few ways you could go about this. Since you want a regular expression, we might try to develop one directly, without going through a finite automaton.

For a string $x$ from $a^*b^*$ to be in your language, its length must be divisible by three. In other words, it must be true that $|x| = 3k$. Let $x = yz$, where $y \in a^*$ and $z \in b^*$. Then $|x| = |y| + |z|$. So we must have that $|y| + |z| = 3k$. There are only a finite number of ways in which this can happen:

$|y| = 3k_1$ and $|z| = 3k_2$, or
$|y| = 3k_1 + 1$ and $|z| = 3k_2 + 2$, or
$|y| = 3k_1 + 2$ and $|z| = 3k_2 + 1$.

Suppose you can create regular expressions $r_1, r_2, r_3$ corresponding to those three cases. Then you can find the regular expression for your language by taking the union. Let's see how that would work for each case.

This case is easy: the number of $a$'s is divisible by 3, and so is the number of $b$'s. We get a regular expression $r_1 = (aaa)^*(bbb)^*$.
Based on the previous answer, this isn't so bad, either: $r_2 = (aaa)^*a(bbb)^*bb$.
Finally, $r_3 = (aaa)^*aa(bbb)^*b$.

We get an easy regular expression by taking the union of these (I use $+$, but $\cup$ is sometimes also used): $r = r_1 + r_2 + r_3 = (aaa)^*(bbb)^* + (aaa)^*a(bbb)^*bb + (aaa)^*aa(bbb)^*b$.


Can a regular language have uncountably many strings? Obviously it can have a countably infinite number of strings. (Take the language descibed by the regular expression 0* as an example.) But can a RL have uncountably many strings? I'm leaning toward no, but I can't really back it up.

No, there are only countably many finite strings over any finite alphabet.  Given an alphabet $\Sigma = \{s_0, \dots, s_d\}$, you can associate the string $w$ with the number $1w$ written in base-$d$, giving an injection from the natural numbers to $\Sigma^*$.  (The reason we use the number $1w$ rather than $w$ is to avoid problems with, e.g., $2$, $02$, $002$, etc. all mapping to the same number.)


Can such a Turing-recognizable language exist? Suppose $\Sigma = \{a,b\}$. Is the following claim correct?

  There exists a Turing-recognizable language $L \subseteq \Sigma^*$ such as its complement is not Turing-recognizable, and for all $n \in \mathbb{N}$ it contains exactly $n$ strings of length $n$.

I'm kind of lost here. Any help would be appreciated.

If $L$ is a recognizable language that contains $f(n)$ strings of length $n$, where $f$ is computable, then $L$ is in fact computable. Given a string $x$ of length $n$, calculate $f(n)$, and then run a recognizer for $L$ on all strings of length $n$. Eventually you will find all $f(n)$ strings recognized by $L$. If $x$ is one of them, accept, and otherwise, reject.


How many times in this pseudo-code is the function F called? For this question, I thought function F called twice but it called three times. Are those three functions were called? F(N), F(K) and F(N-1)?

How many times in this pseudo-code is the function F called?

Main
    Declare K as Integer
    K = 3
    Set Result = F(K)
    Write Result
End Program

Function F(N) as Integer
        If N == 1 Then
Set F = 1
    Else
        Set F = N * F(N - 1)
        Set N = N - 1
    End If
End Function

The function is called 3 times.
F(3)
F(2)
F(1)


Select fixed-size connected induced subgraphs in a graph I have a connected graph with $nk$ vertices, and would like to select $n$ disjoint induced subgraphs with $k$ vertices such that each subgraph is connected, selecting one out of all possible solutions at random. It doesn't necessarily need to be uniformly at random, I just want the possibility of getting any possible solution.
For example, with this graph:

and $k=3$, $n=2$, here is a solution (in fact it's the only one):

And here's one of the two possible solutions for the same graph with $k = 2$ and $n = 3$:

Sometimes this is not possible, like with this graph, for $k = 3$ and $n = 2$:

Is there any (efficient) way of determining whether there is a solution, and if so, selecting one (not necessarily uniformly) at random?

The problem is unfortunately NP-hard.
Thanks to Dmitry for finding this:
https://www.sciencedirect.com/science/article/pii/0166218X85900083.


Learning rule of multilayer neural networks Suppose we have a 2-layer neural network completely connected with $d^{(0)}$ input units, $d^{(1)}$ hidden units and $d^{(2)}$ output units. We consider the error function given by $J(w) = \frac{1}{2}\sum_{k=1}^{d^{(2)}}(t_k-c_k)^2$, where the vector $t = (t_1,\dots,t_{d^{(2)}})$ represents the labels and $z = (z_1,\dots,z_{d^{(2)}})$ represents the values obtained by the network. Suppose that the inputs to the second layer are calculated as $z_k = \sum_{j=0}^{d^{(2)}}y_j w_{kj}$, where $y$ represents the hidden layer output.

I want to know which are the learning rules between hidden and output layer, and between input and hidden layer, for a given activation function $\theta$.

Based on SGD, the learning rule consists in adding to the weights the gradient ot the error function.

For the first one I have tried this. I need to compute the gradient, so I derive $J(w)$ respect to the weight $w_{kj}$ and apply the chain rule:

$$\frac{\partial}{\partial w_{kj}}J(w) = \frac{\partial(\frac{1}{2}(t_k-z_k)^2)}{\partial w_{kj}}=\frac{\partial(\frac{1}{2}(t_k-z_k)^2)}{\partial z_k}\frac{\partial z_k}{\partial w_{kj}} = -(t_k-z_k) \frac{\partial (y_jw_{kj})}{\partial w_{kj}} $$

But I'm not sure about how to continue. If $y_j$ is not dependent of the weight $w_{kj}$, then the derivative turns into $-(t_k-z_k)y_j$, but is this right? Would this be the learning rule for the weights between hidden and output layer?

And for the learning rule between input and hidden layer I don't know how should I start. Any idea would be appreciated. Thanks.

Have a look at backpropagation, which is essentially what you're trying to do here. Wikipedia has a good derivation that follows exactly your example. If you're more into blogs (and who isn't?) have a look at this one, which goes through the steps of backprop in detail.

Best of luck!


Preserving a propositional formula I know I must be getting stuck on notation.  However, I'm having trouble following the logic in Example 1.2 in https://arxiv.org/pdf/cs/0611018.pdf.  They define what preserving a propositional formula means.

So, I'm trying to understand a basic example.
Take X = A or (Not B) or (Not C) as an example Horn Clause.  Define the assignments f1 and f2 by f1(A) = f1(B) = f1(C) = true and f2(A) = f2(B) = f2(C) = false.  Both f1 and f2 satisfy X.

What does it mean to say AND preserves X with respect f1 and f2?

In your example the assignment $f_1\wedge f_2$ is $(f_1\wedge f_2)(A)=f_1(A)\wedge f_2(A)=\text{True} \land \text{False} = \text{False}$.
similarly: $(f_1\wedge f_2)(B)=(f_1\wedge f_2)(C)=\text{False}$ so actually $f_1\wedge f_2 \equiv f_2$.

As they define, AND is preserving $X$ if for every two assignments $f_1, f_2$ that satisfy $X$, the assignment $f_1 \wedge f_2$ (defined by $(f_1\wedge f_2)(v)=f_1(v)\wedge f_2(v)$) also satisfies $X$.


Find minimum time path between two nodes I am trying to write an algorithm for finding best path for an electric vehicle to navigate through network of chargers.

A graph with Vertices representing charges and Edges representing distances among them is provided
Assume that car drives at constant speed (ex. 80 mph) and has a fixed maximum mile Range when its fully charged (ex. 300 miles)
Each charger has a rate associated with it given in miles/minute (how many miles are added for a minute of charging)
Goal is to go from charger A to charger B in minimum amount of time. Assume car is fully charged when you start.
You can stop at multiple chargers on the way and charge the car. You don't have to fully-charge the car at all chargers. You can decide how much time to spend at these chargers
At any point of time remaining range of the car must stay above 0

Output

Find minimum time path between A and B
List of chargers you will visit starting from A and ending at B.
Time spent charging at each of these chargers
Total travel time in minutes

I tried a solution using Dijsktra's shortest path algorithm, but does not fully solve the problem. I don't need help with coding. I don't need help with coding. I want some insights on how to design the algorithm.

This can be done in polynomial time.

I'm assuming:

All our your nodes are charging stations.  If not, you can create a new graph that consists of only charging-stations (including start/finish) by finding the all-pairs shortest paths (or just running Dijkstra's multiple times)
The time spent charging is proportional to the distance driven.  If there are eg. paths that are shorter but require larger charges, the problem becomes much more difficult.

The optimal method will be to drive as far as you can on one charge, then fill up your battery only barely enough to make it to the next charging station.  You can do this by adding weight to each edge $\overline{AB}$ equal to the time needed to wait at $A$ while charging, taking into account the battery's initial charge.

We'll do this by altering Djikstra's algorithm.  We need to make two changes to the algorithm

In addition to giving each node a TentativeDistance, also assign it a CurrentBatteryLevel.  This will be the battery level when reaching the node, before doing any charging.  Set it to full for the initial node.
When expanding the current node and calculating the tentative distance to a neighbor-node, add to the edge-weight the amount of time that will need to be spent charging.  If there is enough charge to make it there, this will be 0, and the potential CurrentBatteryLevel for the neighbor-node will be >= 0.  If there is not, it will be the time required to charge the battery enough so that, when you make it there, CurrentBatteryLevel will be 0.

This works because we're still guaranteed to have found the shortest path to a node when expanding it.  This is true because there are no longer paths with shorter charging times, and we're only altering outgoing edges when expanding nodes (never incoming edges), so the assumptions of Dijkstra's algorithm still hold.

Also, since we only increase edge-weights, never decrease, if you have a heuristic you can still use A*.  It must consistent, since our algorithm breaks if we need to expand nodes multiple times.


Efficiently find smallest unique substring Let's say we have a string $s$. We define a unique substring in $s$ as a substring that occurs only once in $s$. How can we efficiently find such a substring with the smallest length in $s$?
The most obvious solution is in $O(n^3)$ by checking every substring. What if we can preprocess the string?

You can try suffix array approach which find all suffix of a given string of length n in O(n) time.
There are many algorithm to construct suffix array from a given input string.
Look at complete taxonomy here
http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf

For your problem you can use suffix array couple with some additional counter to find solution.


Difference between edges in Depth First Trees I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A).

The result is $M,N,P,O,Q,S,R,T$ (after reversing). Several DFS trees are created during this traversal, and it's the edges between the trees that confuse me. I understand how tree, back, forward and cross edges work in simpler graphs - but this one's harder.

For the example, with the graph

We have the next depth-first trees:

$T$
$S\rightarrow R$
$Q$
$P\rightarrow O$
$M$
$N$

And my question is regarding the edges that connect the trees.

Which are cross edges (like $O,R$), which are back edges and which are forward edges? And giving an example of when they are assigned as back edges / cross edges would be awesome.

You could find a nicely description in CLRS 3ed Chapter 22.3. I extracted the next description from there. There are just four types of edge in a graph.

Tree edges are edges in the depth-first forest $G_\pi$. Edge $(u,v)$ is a tree edge if $v$ was first discovered by exploring edge $(u,v)$.
Back Edges are those edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges.
Forward Edges: are those nontree edges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree.
Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or the can go between vertices in different depth-first trees.

For that, because you're interested in depth-first forest ( graph contains all depth-first search trees) only two types of edges remain:

Tree Edges: edges with a first node without parents in the forest of depth first search trees $G_\pi$
Cross Edges: edges inside depth-first trees with the description above, and those edges connecting those dfs-trees.


state of the art of subset, set containment and partial match queries The subset query problem is defined as:
Given a list D of size N where the entries are subsets of a universe with m elements, create a datastructure that detects for every query-set Q if there exists a set P in D so that Qis a subset of P

I was wondering what are the best known algorithms to solve this problem. I couldn't find any recent publications, just this work from 2002:
Subset Queries

There it is stated, that the subset query problem is equivalent to the set containment problem as well as the partial match problem.

Any help would be appreciated.

I am not sure if this is "state of the art" but take a look at this paper Efficient subset and superset queries.


Books to prepare before reading Knuth's The Art Of Computer Programming (TAOCP) Many people say that TAOCP is not supposed to be read as a book (actually a volume of books), but if I decide to go that way, which math/computer science books/topics do I need to study to help me follow it? There is a related question on stackoverflow but I would like to read the suggestions of cs.se users.

Don Knuth is a teacher, and is always very thorough when he writes.  So one should
expect that he states all prerequisites in his books.

To ascertain that, I went to look in my own issue of the first volume.

Indeed the preface states some prerequisites on page v, which he sums
up into "the single requirement that the reader should have already
written and tested at least, say, four programs for at least one
computer".

Starting page viii, he gives a few words regarding mathematical
content.
"the material has been organized so that persons with no more than a
knowledge of high school algebra may read it, skimming briefly over
the more mathematical portions; yet a reader who is mathematically
inclined will learn interesting mathematical techniques [...]". He
calls his organization a dual level of presentation.

Later he confirms that "a knowledge of elementary calculus will
suffice for most of the mathematics in these books, since most of the
other theory that is needed is developed herein ..."

Hence my best advice is to find out what you need by first reading the
prefaces of the various volumes of TAOCP in the library.  I suggest
adding some lighter reading, such as comics.  You may need it.

A word of warning though. Knuth tends to be too optimistic regarding the brains of other people.


Difference between CRC and Hamming Code I am a bit confused on the difference between Cyclic Redundancy Check and Hamming Code. Both add a check value attached based on the some arithmetic operation of the bits in the message being transmitted. For Hamming, it can be either odd or even parity bits added at the end of a message and for CRC, it's the remainder of a polynomial division of their contents.

However, CRC and Hamming are referred to as fundamentally different ideas. Can someone please elaborate on why this is?

Also why is the CRC compared with the FCS(Frame check sequence) to see if the received message is with or without error? Why not just use the FCS from the beginning? (I might be totally flawed in my understanding by asking this question, please correct me.)

Both CRC and the Hamming code are binary linear codes. One significant difference is that the Hamming code only works on data of some fixed size (depending on the Hamming code used), whereas CRC is a convolutional code which works for data of any size.

So, are CRC and the Hamming code fundamentally different ideas? This is a philosophical rather than a technical question, and so has no definite answer. It could also depend on your point of view. From far away, both are binary linear codes. From up close, there are some crucial differences.


Ehrenfeucht-Fraïssé games, possible mistake in example I was reading up on Ehrenfeucht-Fraïssé and came by this example at http://www.math.cornell.edu/~mec/Summer2009/Raluca/lesson3.html

Shouldn't there be a line between b4 and b2 (or b3 and b1), otherwise I don't see how the duplicator has a winning strategy in 3 rounds. Is this a mistake or ami I missing something?

thank you.

Spoiler wins the $3$-move EF game by picking $a_1$, $a_2$, $a_3$ in any order. You can confirm this by observing that there is a formula of quantifier rank at most $3$ that is satisfied by $A$ but not by $B$, namely:

$$
\exists x\exists y\exists z \ .\  x\neq y \wedge y \neq z \wedge z \neq x \wedge r(x, y) \wedge r (y, z) \wedge r(z, x)
$$

where $r$ is the adjacency relation. Since $A$ has $3$ vertices and $B$ has $4$, Spoiler will also win any $k$-move game for $k\ge 4$, probably the question meant to ask about the $2$ and $3$-move games respectively, instead.


Grouping/Clustering results based on shared values I have a data set that is similar to this:

10,000 jobs with 200,000 applicants which are linked to a job.

I'm looking to cluster the shared jobs based on applicants that they share, am I reinventing the wheel looking to build this or is there a common solution?

Most of the example I found all require a "distance" but I can't see how I could compute one in this case?

Edit: To add, the clustering criteria would be fairly straightforward more than X applicants (say 5) in common, with only a single cluster per job.

You could use the Jaccard distance to compare two jobs: i.e., the distance between two jobs is

$$d(A,B) = {|A \cap B| \over |A \cup B|},$$

where $A$ is the set of applicants for the first job and $B$ is the set of applicants for the second job.  Then, use any standard clustering algorithm with this distance measure.


Wikipedia does not list insertion complexity for arrays - why? Wikipedia does not list insertion complexity for arrays in the list of linked-list implementations.

Is this because insertion operations are not defined on the array ADT?

The array is a fixed-size data structure, and insertions would change its size. Thus they are impossible, which is why Wikipedia says "N/A" for the insertion complexity.

A dynamic array can have its size changed, which is why complexities are given in that column.


If well-founded induction holds, then the relation $\to$ on a reduction system terminates I am trying to understand a proof from "Term Rewriting and All That" by Baader and Nipkow.
Well-founded induction (WFI) is the following statement:

$\forall x \in A(\forall y \in A(x \stackrel{+}{\to}y \Rightarrow P(y))\Rightarrow P(x)) \Longrightarrow \forall x\in A (P(x))$

Here is the proof I cannot understand.

Theorem: If well-founded induction holds, then the relation $\to$ on a reduction system terminates.
Proof: by WFI, where $P(x):=$ "there exist no infinite chain starting from $x$". The induction step is simple: If there exist no infinite chains starting from any successor of $x$, then there exist no infinite chains starting from $x$. Hence, the premise of WFI holds, and we can conclude that $P(x)$ holds for all $x$ i.e., $\to$ terminates.

Why can we define $P(x)$ to be "there exist no infinite chain starting from $x$"?

Well-founded induction, like all other forms of induction, holds for any predicate $P$. That can mean two different things:

Well-founded induction holds for every predicate which you can express in your formal system.
Well-founded induction holds for every subset $P \subseteq A$.

Either way, informally speaking you can define $P$ to be whatever you want.

Formally speaking, you might run into set-theoretic issues, those that separate naive (or elementary) set theory from axiomatic set theory. But presumably this is not the focus of the book, so you can just ignore such issues.

(The gap is that in case 1, you need to show how to express $P$, and in case 2, you need to show that the set $\{x \in A : \text{there exists no infinite chain starting at $x$}\}$ exists.)


Red-blue intersection requirements In the red-blue line segments intersection problem, what does it mean that the red-red (and blue-blue) lines cannot intersect? Does mean mean that the algorithms wont work correctly or does it mean that these kind of intersections will be simply ignored?

In other words, do the fast intersection algorithms require that the are no single-color intersections? Or they can work with such intersections but will find only bi-chromatic intersections?

The red-blue line segments intersection problem can be stated as: "Given a disjoint set of red line segments and a disjoint set of blue line segments in the plane, with a total of n segments, report all k intersections of red segments with blue segments." (From "A Simple Trapezoid Sweep Algorithm for Reporting Red/Blue Segment Intersections", Timothy M. Chan).

The idea, if I understood correctly, is that the problem should be easier to solve than the problem of reporting all intersections between line segments in general. So I'm trying to understand how hard the requirements are...

I guess it depends on the particular algorithm you have in mind. However, the red/blue segment intersection algorithms that I'm aware of require that there are no monochromatic (red/red or blue/blue) intersections. For example, Chans red/blue intersection algorithm builds a trapezoidal decomposition on the blue segments. That does not really work if there are blue/blue intersections as well.

By the way, note that both red/blue segment intersection, as well as  general (monochromatic) segment intersection can be solved in optimal $O(n \log n + k)$ time.


Optimal algorithm for signaling for help? I was thinking about the following problem the other day:

  You are stuck on a desert island with a battery-powered emergency radio.  You know that if you feed enough power into the radio that you should be able to alert someone to your position.  In fact, as soon as you provide the radio enough power to reach someone else, they'll respond back to you and send help.

  The problem is that you don't know where anyone else is, so you have no idea how much power to feed into the radio.  You can assume that the radio can transmit at power levels that are natural numbers.

  What is the most power-efficient way to signal for help?

One inefficient solution to this would be to transmit at power $1, 2, 3, ...$ until you reach the necessary power $n$.  This works, but it requires power usage $1 + 2 + 3 + ... + n = \frac{n(n+1)}{2}$.

The algorithm I currently think is optimal is to instead transmit at power $1, 2, 4, 8, 16, ... $ until the necessary power $n$ is reached or exceeded.  This requires power
$$1 + 2 + 4 + 8 + ... + 2^{\lceil \log_2 n \rceil} = 2^{\lceil \log_2 n \rceil + 1} - 1$$

which is somewhere between $2^{\log_2 n + 1} - 1 = 2n - 1$ and $2^{\log_2 n + 2} - 1 = 4n - 1$

My question is whether or not this is the optimal algorithm for solving this problem, given that $n$ is completely unknown.  I can't seem to find a more efficient algorithm, nor can I find a proof that this is optimal.

Is there a better way to solve this problem?  Or is this the optimal solution?

Your problem is very similar to the well-known cow-path problem, though the details are a bit different. When talking about optimal algorithms, we are usually concerned with minimizing the competitive ratio (a concept from the field of online algorithms), which is the worst ratio between the solution produced by your algorithm and the one produced by the optimal algorithm (in this case, $n$). If your algorithm searches the sequence $a_1 < a_2 < \ldots$ then the competitive ratio is
$$ \sup_n \frac{\sum_{i\colon a_{i-1} < n} a_i}{n}. $$
(Here $a_0 = 0$.)

Suppose we're aiming for a competitive ratio of $C$ (your algorithm gives $C = 4$). Considering $n=1,a_1+1,a_2+1,\ldots$, we must have
$$
\begin{align*}
a_1 &\leq C, \\
a_1 + a_2 &\leq C(a_1 + 1), \\
a_1 + a_2 + a_3 &\leq C(a_2 + 1), \\
&\ldots
\end{align*}
$$
The classical solution to the cow-path problem (Searching in the plane) shows that $C \geq 4$, and so your algorithm achieves the optimal competitive ratio.


Cardinality of ordered n-grams and subsets of those n-grams from a given set Given a set T={A,B,C}, I need to know the cardinality of all ordered sequential n-grams and the total cardinality of all subsets of those n-grams.  To be clear, the subsets MUST retain order as they appear in the original set.

The ordered sequential n-grams of the set T above are {{A},{B},{C},{A,B},{B,C},{A,B,C}} and its cardinality is 6.

The total cardinality of all subsets for those n-grams is sum(1,1,1,2,2,3)=10

So, given set T, what are the formulae for #1 and #2?

Let $|T| = n$. Then

the number of $n$-symbol sequences is $1$, the number of $(n-1)$-symbol sequences is $2$, $\dots$, the number of $1$-symbol sequences is $n$. Thus the number of all ordered sequential $n$-grams is $1+2+\dots + n = \frac{n(n+1)}{2}$.
The total cardinality of all subsets for those $n$-grams is $$\sum_{k=1}^nk(n-k+1) = (n+1)\sum_{k=1}^nk - \sum_{k=1}^n k^2 = \frac{n(n+1)^2}{2} - \frac{n(n+1)(2n+1)}{6}$$

For $n=3$ we have

$\frac{3\times 4}{2} = 6$
$\frac{3\times 4^2}{2} -\frac{3\times 4 \times 7}{6} = 24 - 14 = 10 $


How can I quickly judge whether matrix A is the inverse matrix of B? How can I quickly judge whether matrix A is the inverse matrix of B?
This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution may be related to randomized algorithms.

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random vectors. This method reduces the time complexity from $O(n^{2.3729}$) (regular matrix multiplication) to $O(n^2)$ with high probability. In your case, the matrices $A$ and $B$ would be the matrices you are given, and the matrix $C$ would be the identity matrix.


How to Know Whether a Topic is Publishable in Computer Science Forgive my ignorance, but I am very new to the publishing process in Computer Science. I have some research that I have done involving analyzing data formats used in web-based image processing applications being presented in various IEEE papers. Some are conference papers and some actual IEEE transactions. They all seem to proposing the use of XML or in very few cases JSON as the data formats of choice.

I have read a few IEEE papers done on data traversal speeds involving comparisons made between XML and JSON or one of those two with that of CSVs, but not all three. And I have not found anything that give clear direction for one's reasoning for selecting a particular data format and why. Have I simply missed something? Tis likely, but I wanted to confirm with others first.

I have developed a small proof of concept here, and found some interesting results that I wrote about it here and wanted to see if this is worth trying to publish. Is this a good place to get insights, and share ideas that could be publishable? If so, does anyone have any insight into whether the material I have here is of interest to the scientific computing community? Or is this just a clever IT solution?

I am in the process of refining the paper to include tests done in compiled as well as an interpreted languages. Not to mention the reasoning behind selecting other data formats like CSV or TSV, which appear to much faster to traverse than JSON or XML, but less flexible. JSON appears to be the best choice on average, but more testing is required.

If this is not appropriate, let me know and I will remove this posting. Please also let me know if it is indeed appropriate and if you need more information or less and more of a synopsis.

Thank you in advance.

I'm not from this field, but I believe the following advice holds in any field.

First of all, I will suggest reading related literature; always a good idea. What do people in the field say about this topic? Is there an active community working on it? If not, you may find it hard to publish this work.

In my discipline it is quite acceptable to publish workshop papers. These do not "formally" count as a publication (they don't normally publish proceedings); however, your paper will get reviewed (not very deeply) and if accepted for presentation you will get even more feedback at the workshop itself. You can of course submit it to several workshops: this is perfectly acceptable practice, and I've seen it done with papers that contain only preliminary results.

What's more, this will tell you where your paper stands. If it gets rejected from a workshop on the topic, this is probably a good indication that it's not ready for publication yet.

Important note: it is absolutely fine to submit a paper to more than one workshop; it generally -not- acceptable to make concurrent submissions. That is, submitting to one conference before the outcome of a previous submission is decided. This is highly frowned upon in most communities I'm familiar with (tantamount to self-plagiarism), and will almost certainly make you look very bad. What's more, this will help you for two reasons:

It'll give you a chance to review the feedback you got from the reviewers, and possibly improve your paper.
Communities tend to be small; if you double-submit a paper, there's a non-zero probability that it'll be reviewed by the same people repeatedly (I have had the chance to review the same paper more than once, and I'm fairly junior in my field). Not only will you piss off anyone adversarial to your work by making them read it again, it will also indicate to them that you are not serious and are just "spamming".

So, submit your paper to one workshop, wait for the outcome, then submit to another.

Of course, the tradeoff here is that it'll delay the publication of the work. That said, you may want to acquaint yourself with the field and what's going on by going to a workshop or two, even if your paper is not accepted.

Another alternative is to simply send your working paper to a number of experts in the field and ask their opinion. My experience is that even prominent researchers will seriously answer such queries if the work is comprehensive enough.

Good luck!


what is difference between multilayer perceptron and multilayer neural network? When do we say that a artificial neural network is a multilayer Perceptron?

And when do we say that a artificial neural network is a multilayer?

Is the term perceptron related to learning rule to update the weights?

Or It is related to neuron units?

A perceptron is always feedforward, that is, all the arrows are going in the
direction of the output.  Neural networks in general might have loops, and if
so, are often called recurrent networks.  A recurrent network is much harder
to train than a feedforward network.

In addition, it is assumed that in a perceptron, all the arrows are going from
layer $i$ to layer $i+1$, and it is also usual (to start with having) that all
the arcs from layer $i$ to $i+1$ are present.

Finally, having multiple layers means more than two layers, that is, you have
hidden layers.  A perceptron is a network with two layers, one input and one
output.  A multilayered network means that you have at least one hidden layer
(we call all the layers between the input and output layers hidden).


Question about machine epsilon I am studying over my notes, and there is something I don't understand about $e_m$. We represent the floating point numbers as  $1.d_1d_2...d_t \times \beta^e$. Now, my professor defines $\epsilon_m$ as the smallest $x$ such that $fl(1+x) > 1$. But then she writes

$$\epsilon_m = \beta^{1-t} \hspace{1cm} \text{    (for "chopping")}$$ and

$$e_m = \dfrac 12 \beta^{1-t} \hspace{1cm} \text{ (for rounding)}$$
However, I think these should be $\beta^{-t}$ and $\dfrac 12 \beta^{-t}$, respectively.

The number $1$, and the next number right after, are

$$1.00 \cdots 00 \times \beta^0$$
and
$$1.00 \cdots 01 \times \beta^0$$
where the $1$ is in the $t^{th}$ decimal place. Therefore their difference is $\beta^{-t}$ so if $x = \beta^{-t}$, then $1+x$ is itself a floating point number, so $fl(1+x) = 1+x>1$.

Am I wrong, or are the notes wrong?

Thank you very much.

There is definitely an inconsistency in what you've written here. My guess is that $t$ doesn't mean what you think it means. You are using it here to describe the size of the significand field, that is, the number of digits after the radix point. (It's not a decimal point in general!)

My guess is that your lecturer is using it to refer to the precision. The precision of the floating point format includes the implicit $1$. That is, your floating point number is:

$d_1.d_2 d_3 d_4 \ldots d_t \times \beta^e$

where $d_1$ is always $1$. If you interpret $t$ that way, the two epsilons make more sense.

This is the way that the IEEE-754 standard defines these constants. For example, a binary32 (formerly called "single precision") floating point number has a precision of 24 bits, in that the mantissa is 24 bits. However, the significand field is only 23 bits, because the leading one bit is implicit.


What is the fastest algorithm for multiplication of two n-digit numbers? I want to know which algorithm is fastest for multiplication of two n-digit numbers?
Space complexity can be relaxed here!

As of now Fürer's algorithm by Martin Fürer has a time complexity of $n \log(n)2^{Θ(log*(n))}$ which uses Fourier transforms over complex numbers. His algorithm is actually based on Schönhage and Strassen's algorithm which has a time complexity of $Θ(n\log(n)\log(\log(n)))$

Other algorithms which are faster than Grade School Multiplication algorithm are Karatsuba multiplication which has a time complexity of $O(n^{\log_{2}3})$ ≈ $O(n^{1.585})$ and Toom 3 algorithm which has a time complexity of $Θ(n^{1.465})$

Note that these are the fast algorithms. Finding fastest algorithm for multiplication is an open problem in Computer Science.

References :

Fürer's algorithm
FFT based multiplication of large numbers
Fast Fourier transform
Toom–Cook multiplication
Schönhage–Strassen algorithm
Karatsuba algorithm


Karp reduction from PARTITION to SUBSET SUM PARTITION: Given a set of positive integers $A=\{a_1,...,a_n\}$ does there exist a subset of $A$ with sum equal to the sum of it's complement?

SUBSET SUM: Given a set of positive integers $A=\{a_1,...,a_n\}$ and another positive integer $B$, does there exist a subset of $A$ such that it's sum is equal to $B$?

I was trying to prove that if PARTITION is NP-complete then SUBSET SUM is also NP-complete, by reducing PART to SSUM.

My solution was: let $A=\{a_1,...,a_n\}$ be a set of positive integers. Then if A when fed into PART gives the solution $I=\{k_1,...,k_m\}$ (where $k_i$ are the indices of the members of the solution subset), then we construct $A'=\{a_1,...a_n,S\}$ where $S$ is the sum of $\{a_{k_1},a_{k_2},...,a_{k_m}\}$. $A'$ is a solution to SSUM.

My problem with this is that this goes only one way, meaning that we can't show that given A' then A is a solution to PART. Is this a problem? and how could i modify the proof to cover it?

Let's say we have a canditate set $A=\{a_1,...,a_n\}$ to feed as input to PARTITION. There is a transformation in polynomial time $f$, with $f(A)=(A,B)$, where $B=$${\sum_{i=1}^n a_i }\over 2$.
Then $A$ is a solution to $PART$ if and only if $(A,B)$ is a solution to $SSUM$.
So we have $PART \le_m^p SSUM$


In what cases is graph rewriting not enough to avoid duplicate work? As I understand, evaluating something like the following in normal order evaluation is inefficient due to duplicate work:

double x = (x,x)
main     = double some_hard_computation

I remember someone telling me

That there are two ways to avoid this: strictness analysis (to recognise that double is strict in its one argument, and then deviating from normal order evaluation and evaluate the argument first) and graph rewriting (store pointers to some_hard_computation such that both elements of the tuple point to the same computation, and evaluating one side of the tuple automatically evaluates the other side as well).
That neither of the ways are sufficient on their own to avoid all cases where duplicate work can be introduced, and that it is best to apply both when writing a compiler.

I can imagine that strictness analysis can be hard, but in what concrete case can duplicate work be introduced when utilising graph rewriting? Or is either of the two bullet points above incorrect?

Note: while strictness analysis is done statically (as far as I know), graph rewriting is an evaluation strategy, not a compiler optimisation. It attempts to solve the same problem as the strictness analyser, but on a different level (runtime vs. compile time).

Consider this program:

f (m : Nat) x y = (x, if H(m,m) then x else y)

my_f = f my_number
my_f hard harder

where H(x,x) returns True if Turing machine number x halts on input x and False otherwise. Detecting duplicate work (always) would mean solving the halting problem, no matter whether you want to do the analysis statically or dynamically.

Hence, no method can be complete.


NP-Completeness of modified decision problems Suppose we have a NP-Complete decision problem like independent set or finding matching in graph theory and we change the greatness or smallness of the condition of that problem i.e. change the direction of the inequality in the problem's definition ($ \ge$ or $\le $).
For example in independent set problem when the condition is $|V'| \ge k$ and I change it into $|V'|\le k $. Are problems modified in this way still NP-complete?

It depends on the problem. For, say, clique or independent set, the problems become trivial if you change the direction of the inequality: $\emptyset$ is always a clique/independent set of size $\leq k$.

On the other hand, the travelling salesman problem remains NP-complete if you ask for a tour of length at least $d$ instead of at most $d$.  To see this, suppose that you want a tour of graph $G$ of length at most $d$. Let $m$ be the length of the longest edge in $G$, and let $G'$ be the graph that's identical to $G$ except that, if an edge has length $\ell$ in $G$, then it has length $m-\ell$ in $G'$.  Now, any tour of length $t$ in $G$ corresponds to a tour of length $nm-t$ in $G'$ (where $n$ is the number of vertices), so $G$ has a tour of length at most $d$ if, and only if, $G'$ has a tour of length at least $nm-d$.


Are C standard library functions considered part of C programming language Do we consider functions like printf part of C language even if it's not a keyword in it.

The “C programming language“ is defined by a document that defines the syntax and the semantics of programs, and the C standard library. So both are part of the “C programming language”.
However, in CS the term “language” is used in a different way, as a set of strings. You can define a language based purely on the syntax In the C Standard document - that allows you to distinguish between strings that are formally in the language and those that are not, but you still have no clue what a program would do.
You can also incorporate some semantic rules, so that for example int a[-10] or int i = "String" are not considered to be part of the language.


What are the advantages of online learning when training neural networks? Stochastic gradient descent with a batch size of 1 is apparently used to learn from single examples as they arrive, but I don't understand why you would use such a small batch size instead of batching training inputs together.

Batch learning and online learning both have their place.  Generally speaking batch learning will train your neural network to a lower residual error level, because the online training can sometimes have one training undo the effect of another.  However, online training has a few advantages:

Online learning schemes learn "faster."  In some cases, determining how many samples you need can be difficult, and sample gathering may be costly.  Online learning lets you see the progress of your training as the number of samples increases, potentially saving on sample gathering costs once it reaches an acceptable error.
Online learning schemes can be done during operation, which can be valuable.
Online learning schemes are more effective for dealing with data sets that are not stationary.  It is easier for the batch methods to come up with highly specialized solutions which work well for the test samples, but do not capture a general solution.


Better algorithm for aggregating data from various LDAP systems I have 10 LDAP systems which contain users and groups in the form of objects. Each user / group is identified by a distinguishedName like name/systemName where name is name of user or group.

Group objects store which users are members of the group.

GroupA = {UserA, UserB, UserC ....}
GroupD = {UserF, UserB, UserK ....}

This information is not stored in the users object. User objects have user related attributes.

UserA = {name="ABC", dob="x/x/x", }
UserB = {name="PQR", dob="x/x/x", }

I want to make a system, which will query all systems to get user and group objects and show them on GUI this way

UserA = {name="ABC", dob="x/x/x", memberOf=[GroupA]}
UserB = {name="ABC", dob="x/x/x", memberOf=[GroupA, GroupB]}

There are millions of users and millions of groups in these systems overall.
The software I have created runs on various machine simultaneously. The software is written in Java.

I am using this approach to achieve this:

Start my program on one machine - Machine#1
Get all group objects from all the systems one by one and store them in memory store with key as user and value as list of group names
Once all the groups are queried and stored in memory store, then fire my program on other machines too
Other machines will copy the memory store created on Machine#1 to their machine (using third party lib - ehcache)
Program on each machine will query some set of Systems (Machine#1 will query system 1,2,3; Machine#2 will query 4,5,6 .. and so on)
Get all user objects and as I receive each user object, query memory store to see if user has any groups attached. If yes, pick them and store in DB?
Once all the programs on all machines are finished, we have result in DB which can then be shown anywhere

This approach has following disadvantages:

Consumes lot of memory (memory stores uses 20 GB RAM on one machine)
Memory store which needs to be replicated on other machines is not so stable process
Memory store is only built on single machine. This takes about 3 hrs to complete. During this time, other machines are idle, which is waste of resources.

End goals of application should be:

Best performance possible
Minimal wastage of computing time
Data (user objects showing groups) should be available in said format. The format cannot be changed as there is dependency with other downstream systems.

Is there a better approach to achieve the same ?

Your algorithms seem fine.  I don't think you need better algorithms; I suspect what would help most is more on the engineering and implementation side.

At a high level, I would say that your design seems good enough as is.  If the primary objection is that it requires 20GB of RAM, well, buying RAM is a lot cheaper than spending a day of a software developer's time to implement a more memory-efficient solution.  So my primary advice would be to order some more RAM and call it good enough.

But if you still want to push on, I'll offer some other reactions...

Millions of users and groups is a fairly small data set.  20GB of RAM seems excessive for that.  Suppose there are 5M users, and each user is a member of 5 groups on average (say), and each group name is 10 characters long on average.  That corresponds to 50 bytes of data per user.  Add some overhead and round up and I'd estimate something like 80 bytes per user.  Yet your current data structure seems to be using 4KB per user.  That seems 50x too large; I would have expected something like 400MB would be sufficient.

Therefore, I'd suggest you do some memory profiling and look into why your in-memory store is taking up so much memory.  Perhaps you are using an unnecessarily inefficient data structure or hashmap implementation.  Keep in mind that you don't need to store the entire user object and group object (with all their attributes) in memory.  All you need to store in memory is the name of the user (a string) and the names of the groups they are in (a list of strings); the attributes can be stored in the database.  There are other techniques for reducing memory, such as sharding the data structure across multiple machines, but that hardly seems necessary or worth the effort.

Also, I wonder whether it's really necessary to run on multiple machines.  With only a few million users, I would have expected one machine to be more than adequate.  So if you care about the time to completion, you might want to look into that.  If you can do it on one machine, that will be simpler to implement, simpler to deploy, simpler to maintain, simpler to manage, and will reduce your stress about tying up 20GB of RAM on multiple machines.  I would have expected that the rate-limiting step is the number of LDAP queries you can make per second, so you could investigate what is keeping that down.  Perhaps you can have multiple threads making LDAP queries in parallel.  Perhaps you can reuse the same connection for multiple queries, to avoid connection setup and teardown costs.  Maybe you can run this on the same machine as the LDAP server to reduce network overhead.  Maybe you can think of some other speedups.

But overall, my guess is that this is a problem better solved by a beefier hardware rather than a software developer's time to optimize the code; and if you do want to improve the software, you're more likely to see gains from focusing on quality of implementation rather than algorithms.

Based on your comments, here is an alternative data structure that might save memory.  Assign each user and each group a unique integer ID (incremented by one for each new user/group).  Keep a mapping from name of user -> ID of user (with a hashtable) and a mapping from user ID -> user name (with an array); this is probably doable with 2-4GB, based on your numbers.  Do the same for groups; that's probably much less.  Then, keep a mapping from user ID -> array of group IDs that the user is in; that's probably doable with another 2-4GB.  All in all, I'd expect this could reduce your memory consumption to 4-8GB instead of 20GB.  You might be able to get further reduction by storing names in UTF-8 rather than UTF-16.


Find out the largest LCM of the partitions of n I want to find out an algorithm to find out the largest least common multiple (LCM) of the partitions of an integer $n$.

Example:  $5 = 1 + 4$, $5 = 2 + 3$, since $\mathrm{LCM}(1,4) < \mathrm{LCM}(2,3) = 6$, the largest LCM of the partitions of $5$ is 6.

The definition of "partition" is the standard definition of it. In order to make the problem more clearly, I will take n = 10 as an example. The largest LCM if the partitions of 10 is 30, since 10 = 2 + 3 + 5.
More examples(Let g(n) be the answer that I want to get):
g(11) = 30
g(12) = 60
g(13) = 60

I want to find out an algorithm that can get the largest LCM in 1 second with the n less or equal to 250.

It seems that this a competition problem. Your best bet is to pre-calculate maximum values for all numbers(250 isn't very big) and store it into an array. That would be the best bet as this can give you timing near to zero.


First Sets: If $A \to Ad\ |\ c$, what is $First(A)$? Suppose that we have a grammar with the following rules:

$$S \to Aa\ |\ b\ |\ \varepsilon\\
A \to Ad\ |\ c$$

From looking at it I already know that $First(S) = \{b, \varepsilon, c\}$. My question is:

How to determine $First(A)$?

For instance, by looking at the rule $S \to Aa$ we know that $First(S)$ must include $First(A)$. $First(A)$ already includes $c$ (that's why $c \in First(S)$). but how to handle the rule $A \to Ad$.

Just by applying the algorithm for finding the $First$ set blindly, I will have that $First(A)$ "includes" $First(A)$, which confuses me.

As far as I understand in $A \to Ad\ |\ c$ there is a left recursion. By eliminating it we get the following rules

$A \to cA'\\
A' \to dA'$

Does this mean that $First(A)$ only contains $c$?

Does this mean that I can ignore a rule with left recursion and just look at the other (non-recursive) rules under that variable?

Thanks!

The grammar you have presented is left linear grammar. The production $A \rightarrow Ad$ in when transformed into $FM$, $A$ becomes state & an edge with $c$ terminal from $A$ to $A$ (self loop). So its clear for this particular grammar $First(A)$ is $c$.

Moreover, your approach is also correct or primarily correct.


I cannot find an invariant for the following program I have the following:

(|$y=0; x=c$|) while(x > 0){y=y+a; x=x-1;} (|$y= a*c$|)

This seems like a fairly simple program and I can intuitively tell that the post condition $y=a*c$ is true when the loop terminates, but I cannot a find a good invariant. Of course, I think I can say the variable $a$  is an invariant, but I don't think that it would prove the partial correctness of this program.

Any help is greatly appreciated.

Figure out what the value of y is, depending on x, a, and c. Prove that your formula is correct before the first iteration, and prove that if it is true before an iteration then it is also true after the iteration.


Computer graphics: Linear Interpolation I have two vector points $p_1$ and $p_2$. Each point has a color value $c_1$ and $c_2$.
Now using linear interpolation, I would like to get the color value at point $p_3$.

Concrete example:

$\qquad \displaystyle p_1 = (1, 3) \text{ with } c_1 = (2, 4, 1)$
$\qquad \displaystyle p_2 = (4, 4) \text{ with } c_2 = (3, 1, 2)$

What color does $p_3 = (2,3)$ have?

Normally in graphics, you interpolate values across a line like so:

Point $A$ has value $V_A$ and point $B$ has value $V_B$, then you want to blend the value/color linearly between them as $C$ moves between $A$ and $B$. To do this, you first calculate the ratio (or percentage) of how far $C$ lies across the line $\overline {AB}$. This is equal to $\overline{AC}$ over $\overline {AB}$. Thus the ratio is calculated as follows:

$$
t=\frac {(C-A)}{(B-A)}
$$

Once you have this ratio, you can use it to find the interpolated value between $V_A$ and $V_B$, since they should have the same ratio.

$$
t=\frac {V_C - V_A}{V_B - V_A}
$$

The unknown variable here is $V_C$, so solving for $V_C$:

$$
(V_B - V_A)t=V_C-V_A\\
V_C=(V_B - V_A)t+V_A
$$

However, this assumes that point $C$ lies on the line $\overline {AB}$. If it is not on the line, then you can't really "interpolate" in this way without some additional definition of what you want to interpolate. For example, if $C$ lies far below the line, then you can't really compare $\overline {AC}$ to $\overline {AB}$ like this; the ratio can be greater than 1, even though $C$ is "in between" them. So in your example, point $(2,3)$ is off the line. You have many possible variants.

For instance:

You can interpolate between the distances of $\overline {AC}$ and ${BC}$. You would thus create a new straight line, $\overline {ACB}$ (even though in the graph it would be an angle) and do the above interpolation on that.
You can interpolate a particular color to a dimension. For example, you take the values $A_x$, $B_x$ and $C_x$, and interpolate $\overline {A_xC_x}$ over $\overline {A_xC_xB_x}$, and use that for Red, then use $y$ for Green etc. However this works better for 3 dimensions, where each dimension can correlate to a color.


Finding libraries of formalized mathematics I want to formalize Interval Newton Methods in Isabelle. As a research, I have the curiosity of whether there is anything done in the field. For that, I need to know what mathematical contents have been formalized in different proof assistants.

For Isabelle, this is easy: just google the Archive of Formal Proofs. What about the others? Can you help me to complete this list (taken from Wikipedia's table for proof assistants) providing links to the relevant libraries of formalized mathematics:

ACL2 1, Agda, Albatross, Coq, F*, HOL Light, HOL4, Isabelle, Lean, LEGO, Mizar, NuPRL, PVS, Twelf?

If you know of other libraries you are very welcome to add the corresponding tool.

Additions:

Is https://coq.inria.fr/ the primary place to look for proofs written in Coq?

Metamath has a HUGE chapter-organized archive of formal theorems:

http://us.metamath.org/mpeuni/mmtheorems.html

Besides that, Freek Wiedijk's QED manifesto is always a good starter for future formalizers. And his list of top 100 formalized theorem is an ever-encouraging source of formalized ideas:

http://www.cs.ru.nl/~freek/100/

At the end of that page, he provides another list of desired but-still-missing formalized theorems. The one that I personally desire, is $\mathrm{IP=PSPACE}$.


If Halting problem is decidable, are all RE languages decidable? Assume the halting problem was decidable.
Is then every recursively enumerable languagerecursive?

While we know for sure that the halting problem is (and always will be) undecidable by a Turing machine, we can take the following approach to investigate your question:

Assume that we have a magical machine that can solve the halting problem. We call this machine an oracle. We can now wire this machine into a Turing machine, creating Turing machines that can solve the halting problem.

Unfortunately, the same problem we had with the original Turing machines occurs again: we can enumerate our oracle-enriched Turing machines. We can define the function that computes $T_i(i)+1$. This function cannot occur in our enumeration, because it differs from all Turing machines. In short, if we have machines that can solve the halting problem, we get a new halting problem for those machines.

This principle gives us a hierarchy of uncomputable functions (called the Turing hierarchy). Some functions become computable if we have machines with an oracle for the first halting problem, while others stay incomputable. If we give our machines an oracle for the second level halting problems, more functions become computable, but some functions will always be uncomputable.

And yes, languages that are only recursively enumerable to regular Turing machines are fully recursive to oracle-enriched Turing machines. Let's use the following definitions:

A recursive set is one for which there exists a TM which can answer yes if a given element is in the set, and no if it isn't.
A recursively enumerable set is one for which there exists a TM which can answer yes if a given element is in the set and compute indefinitely if it isn't.

In the second case, we can create an oracle enriched TM which checks if the non-enriched TM halts. So the enriched TM can give a yes-or-no answer.

Of course, there will be new languages which are recursively enumerable in the oracle-enriched world, but not recursive. In the non-enriched world, these languages were not enumerable in any way.

NB: In general, the phrase 'oracle' can mean any addition to enrich a Turing machine, not just one to solve the halting problem. If the type of oracle isn't clear from context a phrase like "a Turing machine with an oracle for the halting problem" should be used to avoid confusion.


What is the purpose of ϵ-transitions in PDA? $A = \{a^i b^j c^k\mid i = j\text{  or } j = k; i, j, k \ge 0\}$.
In its push down automaton should not there be the red colored transition instead of the black colored one?

Yes, you could substitute the red transition for the black one below and have an equivalent PDA. With the black one, you allow the possibility that when reading $\mathtt{b}$s, you make a nondeterministic switch to the state where you expect to see a $\mathtt{c}$. If you do, it's as if you followed the red transition. In other words, either PDA will accept a string in $A$.

By the way, you could do a similar thing between the first and the second states of the upper branch.

The moral is that here are many roads to the top of the mountain, grasshopper.


Urgent Flag of TCP, Computer Networks The Urgent Flag(URG) is set whenever the sender's Application Layer wants to send some urgent data to the receiver. In this case, the Transport Layer does not wait for enough data to achieve maximum segment size. Now, my question is how do the routers in between recognize that the packet needs to be forwarded urgently(they do not have the transport layer)?

They don't.  The urgent flag doesn't affect the handling of the packet by routers.  The urgent flag is an instruction to the TCP stack on the destination host, not an instruction to routers along the path.


Help interpreting this deadlock question I have this assignment question but I am a bit unsure how to go about answering it. The question is as follows and accompanied by the image below:

Three processes are competing for six resources labelled A to F as shown
below.

Using a resource allocation graph, show the possibility of a deadlock in
the implementation above.

I know how to do the graph but what I am struggling to understand is, do I take the Release(); methods into consideration or only the Get(); methods. And also, would P0() access resources A, B and C first or will each process run simultaneously meaning P0() access resource A, P1() access resource D and P2() access resource C, and then the second set of Get() methods are requested simultaneously? Lastly it does not specify how many instances (dots) are in each resource, is there any indication as to how to determine/go about working with this? As soon as I can clear up these misunderstandings I can draw the diagram

Here is one bad scenario:

P0 obtains A and B.
P1 obtains D and E.
P2 obtains C and F.

At this point, we have reached deadlock, since P0 is waiting for P2 to release C, P1 is waiting for P0 to release B, and P2 is waiting P1 to release D.


reduction from SET-COVER to VERTEX-COVER I've come with an idea for reduction from the set-cover problem to the vertex-cover problem, But I'm not sure if this reduction is correct. I saw in  this post's comments that "There cannot be a nice reduction of this sort".

Consider the set of $S$ to be $S_1,...,S_n$ where the element of $S$ is $s_1, ..., s_m$. In the graph $G=(V,E)$ for each $S_i$ there is a vertex, and an edge from $S_i$ to $S_j$ will be iff there is some element $x\in S_i \land x\in S_j$.

is this reduction even right?

No, since  {{0,1},{1}}  and  {{0,1},{1,2}}  yield isomorphic graphs

but the sizes of their minimum set covers are different.


Is there a decidable algorithm to compose two well-behaved recursive functions that work on a recursive tree datatype? Let the following datatype be defined:

 data T = A | B T | C T T

That is, B, B T, B (B T), C A A, C (B T) A and so on all are members of T. Now, suppose we define two functions that operate on that type:

f :: T -> T
f A = A
f (B x) = B (B (f x))

g :: T -> T
g A = A
g (B x) = B (B (B (g x)))

There are restrictions on the definition of f and g: first, recursive calls can only be applied directly to a subterm of one of the inputs (guaranteeing termination), and second, they can't use any datatype other than T on their bodies (consider T is the only existing type). In this case, we know that the following function:

h :: T -> T
h A = A
h (B x) = B (B (B (B (B (B (h x))))))

works as the composition f . g. My question is, is it possible/decidable to find the composition of f and g in this form - that is, without any reference to f and g themselves? What is the name of the problem I am trying to solve?

If the functions are sufficiently well-behaved, as in your example, you can express f and g as regular transducers for trees.  Then you can compute the composition of two such transducers, which will also be a regular transducer (I believe), and convert it back to a Haskell function.

Another approach: in some cases, simple let-substitution might suffice.  For instance, given your f and your g, we can identify their composition fg via the following sequence of steps.  We know fg = f . g, so plugging in the definition of g, we get:

fg A = f(g(A)) = f A
fg (B x) = f(g(B x)) = f(B (B (B (g x))))

Now plugging in the definition of f, we get:

fg A = A
fg (B x) = B (B f(B (B (g x))))

Continuing to plug in the definition of f, we get:

fg A = A
fg (B x) = B (B (B B( f(B (g x)))))

And plugging in the definition of f once more:

fg A = A
fg (B x) = B (B (B B( (B (B (f(g x))))))

which simplifies to

fg A = A
fg (B x) = B (B (B (B (B (B (fg x)))))

And now you have your desired recursive definition of their composition.  Notice that this is the same as the function h you wanted to get out.  As far as I know, there's no guarantee that this procedure will always work, but it is easy enough to apply.


Need help understanding which values can be inserted into a specific node in a binary tree I am studying binary trees and I am failing to see what numbers can be inserted into this specific node position. The values to pick from are : 16, 24, 36, 45, 49, 51, 58.

I have tried values 24, 36, 45, and 16, 24, 36. I have tried these values because going from left to right, they go in increasing order. Though this is not working and I'm not quite sure why. I'm not sure why what I am selecting is wrong. Any help trying to solve my confusion is appreciated.

Binary trees can serve many different purposes. They don't necessarily need to be in an ordering like such.

Note that below, I hid key parts of the solution. You can view them by hovering over with your mouse, but I encourage you to try to solve it using clues from my response without seeing the actual answer.

For your particular problem, it appears that the ordering of the tree is such that all nodes to the 'right' have a value greater than our root (global or local root, doesn't matter) and all nodes to the 'left' have a value less than our root.

With this in mind, $u$ must be greater than our root node, so

  $16$

is ruled out. Then, by taking $u$ to be our next (local) root node, $u$ must be greater than the maximum value of its left subtree and $u$ must be less than the minimum value of its right subtree. From this, we can see that

  $28 < u < 50$.

This rules out

   $24, 51, 58$.

Therefore, the answer to your problem is

  $36, 45, 49$


Can a graph have multiple identical elements? Can a graph have multiple nodes that have the same value ? For instance, could a graph holding numbers have the same number present multiple times across the itself ?

My current approach is to not allow the insertion of the same element multiple times, and to instead enable an element to have an associated value, is it correct ?

Thank you.

Graphs don't have values.  Graphs don't hold numbers.  You don't insert a value into a graph.  Graphs have vertices and edges.

You can augment a graph to associate each vertex (node) with a number, if you wish.  If you do that, it's up to you to define whether or not you allow two different vertices to have the same number or not.  There is no universal answer.


Time complexity of Hash table lookup Suppose I have a hash table which stores the some strings. Let the index/key of this hash table be the length of the string. what is the time complexity of checking if the string of length K exists in your hashtable? is it O(1) or O(k) ?

If the hash function takes the whole string into account, then the hash calculation takes $\Omega(k)$ time where $k$ is the length of the string. So the hash table lookup takes $\Omega(k)$ time.

The hash table lookup takes $\Theta(k)$ time if the hash calculation is done in linear time in the length of its input, which is typical for hash functions, and the lookup of the value takes $O(k)$ time. That part is usually not the case. With a typical hash table, looking up the bucket for the hash value in the table takes constant time $O(1)$ with respect to the length of the string $k$ and the size of the hash table $n$. But that's not the end of the lookup.

If the bucket is empty, the value is absent and the lookup ends there, having consumed $\Theta(k)$ time. If the bucket contains a value, you need to be compare it with the string that you're looking up, and that takes $O(k)$ time. If the value in the bucket is equal to the value that you're looking up, the lookup ends there, having consumed $\Theta(k)$ time. But what if the value is different? What happens next depends on the variant of the hash table data structure.

In a variant where collisions are handled by growing the hash table until there are no more collisions, the lookup ends here and the cost of the lookup is indeed $\Theta(k)$. This variant has efficient lookup, but pays for it by making addition potentially very expensive (depending on the growing strategy when a collision happens).
In a variant where collisions are handled by putting the value in the next bucket (for some traversal strategy), the search can potentially cover the whole table, with one string comparison for each bucket. The worst-case cost of each string comparison is $\Theta(k)$ (with a typical string comparison algorithm, the worst case is reached if the strings have the same length and differ towards the end). In the worst case, the total cost of the search is therefore $O(k \cdot n)$.
In a variant where collisions are handled by storing values that land in the same bucket in a secondary lookup structure (such as a list, a hash table with a different hash function, or a search tree), the cost depends on what the secondary data structure is. It's unlikely to be $O(1)$ with respect to the number of values in the bucket, so the worst-case cost of the lookup is not $O(k)$.

Hash tables only have constant-time operations in the average case with some “reasonable” (or not) hypotheses over the data, not in the worst case. See also (When) is hash table lookup O(1)?