Top Down Insertion in a B Tree I have a B-Tree of order 5. So the keys are between $\lceil n/2 \rceil- 1 \leq keys \leq n - 1$ and children are between $\lceil n/2 \rceil \leq children \leq n $. Am I doing it right? So a full node would be of 4 keys, how do I split that, because when I split that full node, I get uneven keys in any of the children.

Example:
$\{G\}$ at level $0$,
$\{A, C, E\}$ and $\{H, K, N, Q\}$ at level $1$

Here $\{H, K, N, Q\}$ is a full node, when I insert T, I must pre-split $\{H, K, N, Q\}$, I get one key in either of the subtree which is wrong as the selection of keys suggest that they must be between 2 and 4.

What am I doing wrong?

It seems you are doing nothing wrong. Like you say, for a B-tree of order $n$ the number of children is between $\lceil n/2 \rceil$ and $n$, the number of keys is one less.
For $n=5$, keys are between $2$ and $4$. When you add a key to a node of size $4$, you get two new nodes of size $2$ and one new key which is pushed upwards. When this happens at the root, a new root with a single key is formed.

Your example. Add $T$ to the tree. At the root $G$ go right, to $\{H,K,N,Q\}$. With $T$ this becomes $\{H,K,N,Q,T\}$ which is too heavy and we split into $\{H,K\}$ and $\{Q,T\}$. Middle key $N$ is pushed upwards to the root. In the new configuration the root $\{G,N\}$ with two keys has three children $\{A,C,E\}$, $\{H,K\}$ and $\{Q,T\}$.


Prove that the language of non-prime numbers written in unary is not regular Im trying to prove that the following language is not regular.
$$\text{Notprime} = \{a^n \text{where \(n\) isn't prime}\}
  = \{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\}$$

Heres what I have:

"If Notprime were regular, then its complement would be regular also. However, the complement of Notprime is the language Prime, hence Notprime is non-regular."

Is this the right way of proving it? Any help is appreciated!

This proof is correct, the complement of a regular language is indeed a regular language (and dually the complement of a non-regular language is non-regular). Your proof relies on the assumption that Prime is not regular. If this was given as an exercise and there wasn't an earlier question about Prime, then the intent of the exercise was probably that you prove that Prime is not regular (or directly prove that Notprime is not regular, which is about as easy).

The usual method in elementary exercises to prove that a language is not regular is the pumping lemma. It works for this example. See How to prove that a language is not regular? for more methods, and questions tagged pumping-lemma for examples of using the pumping lemma.

For an with a single letter, there is a general form for all regular languages: they are the languages that, for sufficiently long words, consist of the union of several arithmetic progressions with the same coefficient: $\{a^{ak+b} \mid k\in\mathbb{N}, b \in B\}$ for some fixed $a$ and some finite set $b$. See What are the possible sets of word lengths in a regular language? for a more precise description and a proof. The set of primes, or the set of non-primes, does not have this structure since there are growingly large gaps between primes.


Question of DFA closure properties? I have some question about DFA Language properties.

Does closure under intersection and complementation imply closure under union?

Does closure under intersection and union imply closure under complementation?

Thank you

Does closure under intersection and complementation imply closure under union?

This is immediate from De Morgan's laws.

  Does closure under intersection and union imply closure under complementation?

This one is slightly trickier. The answer is no.

Both intersection and union are what is called "monotone". That means that, if you make $X$ or $Y$ bigger then $X\cup Y$ and $X\cap Y$ can't get smaller. By induction, you can prove that any operator defined using only intersections and unions must also be monotone. But complement is not monotone: when you make $X$ bigger, its complement definitely gets smaller. So complement cannot be defined using only intersection and union.


Is it possible to write an AND gate using XOR gates? How could I express an AND gate using only XOR gates ?

You cant.

Since $XOR$ is associative, i.e. $(x_1\oplus x_2)\oplus x_3=x_1\oplus(x_2\oplus x_3)$, you can only implement functions of the form $x_{i_1}\oplus...\oplus x_{i_k}$ where $x_{i_j}\in\{x_1,x_2\}$. This is equivalent to (depending on the parity of the number of instances of $x_1$ and $x_2$) either 0, $x_1$, $x_2$, or $x_1\oplus x_2$, which are not equivalent to AND.


How to make NFA remember its first step? I have to design an NFA that will take the strings "token" and token.

I can use $\lambda$ or " to the first state, but then how do I know on the final state if it should have end quotes or not?

NFAs have finite "memory", and you need to store one bit of information: whether the first symbol was ".

   Copy the automaton for tokens. If your string starts with ", move to one copy; if not, to the other. The first copy then requires a trailing " to accept, the second one does not.

 In general, you can implement any finitely-bounded counter like this: just copy all states as many times as you need.


Higher order rewriting theory and critical pairs with the beta rule In a higher-order pattern rewrite system, one specifies rewrites on beta
normal forms of terms.  Is it possible to have a rewrite like:

$\gamma := \lambda x . F(m) \to F(\lambda x . m)$

for some function symbol $F$ and $m$ in $\beta$-normal form?  If so, then there is a "critical pair" between $\gamma$ and $\beta$

$F(m) [t/x] \leftarrow (\lambda x . F(m)) t \rightarrow (F(\lambda x .m )) t $

On the other hand, is there any reason to require $\gamma$ go the other direction?:

$F(\lambda x . m) \to \lambda x . F(m)$

This would avoid critical pairs with $\beta$, but may in practice be less natural.

If the former is possible, can one still conclude confluence if all critical pairs are development closed?

The theory of higher-order critical pairs can indeed handle this example, as outlined in the following article:

Higher-Order Rewrite Systems and their Confluence, Richard Mayr & Tobias Nipkow

There are several different notions of higher-order rewrite systems, and several of them are able to handle your example, including those of the paper.

The critical pair lemma is still true: if every critical pair is development closed, and the system is terminating, then one can conclude that it is confluent. The second condition is necessary though, in particular, $\beta$-reduction on untyped terms can muck things up.

This means that completion is still a meaningful operation in this setting.

At any rate, your second rule seems a bit more natural in a termination context, where $F$ is "pushed towards the leaves", but obviously it depends on the meaning of the symbol.


Finding the largest 3-clique-free induced subgraph Consider this problem:

Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that:

$G'$ is an induced subgraph of $G$
$G'$ has no 3-cliques
$|V'|$ is maximal

So the least number of vertices must be eliminated from $G$ so that 3-cliques are eliminated.
An equivalent problem would be to find a 2-coloring for $G$ such that if $(v_1, v_2, v_3) \in V$ and $((v_1, v_2), (v_2, v_3), (v_3, v_1)) \in V$,

$(v_1.color == v_2.color \wedge v_2.color == v_3.color \wedge v_3.color == v_1.color) = False$

The (absolute) difference between the number of nodes with color 1 and the number of nodes with color 2 is maximal.

Can anyone think of a polynomial-time algorithm to solve one of these problems?

Both definitions leave your problem NP-hard, and have been answered on cstheory.

Interpretation 1, where you require the largest triangle free sub-graph, is NP-Hard and has been answered here.
Intepretation 2, where you need a partition such that both the induced sub-graphs are triangle free, has been answered here.

Note that the answers I linked to are for general $H$-freeness and are a class of $NP$-Hard problems.


How does a Trie work? Specifically, many say that to speed up an HTTP routing code going from regex to a Trie is the solution. Sometimes also a compressed Trie or Radix Tree.

The problem though is that after reading everything I think I could read from Wikipedia to blog articles and even Stack Exchange answers I couldn't wrap my head on how this is implemented. Maybe it's simpler than I think but I'm looking at it from the wrong perspective, no idea.

So let's take this HTTP request:

GET /hello HTTP/1.1
Host: www.stackoverflow.com
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)
Accept: */*

With a Trie are you going to iterate on GET, then "/" then "hello" then "HTTP" then "1.1" etc until you get to the end of the request with matches or does it work differently than this?

               root
           /  /   \  \
         GET POST PUT DELETE
         /
       "/"
       ...
       /
    "HTTP"
      /
     "1"
     /  \
   "0" "1"

I have a hunch that that's not exactly the case because it has the potential to lock a loop or function where it's executed in, or waste resources if event'ed. Given the fact that this solution is considered when the HTTP routing itself becomes a problem it must work differently?

At it's core a trie is a tree-shaped deterministic finite state machine (no loops, no merges). They work best when you have a preset number of keywords to search for.

The root is the start state and the leaves are all final states but each with its own action.

However for parsing the http optimally one wouldn't use a pure trie. BEcause the input is mostly freeform you are better off using a custom state machine.


LTL to automaton translation that can only read disjunctions of labels per transition Is there any automaton (or automaton translation) as expressive as LTL that can only read disjunctions of atomic propositions per each transition? Standard LTL-to-automaton algorithms allow the automaton to read conjunction as well as disjunction of atomic propositions.

The models of an LTL formula $\varphi$, with atomic propositions $P$, are infinite words $w = \sigma_0\sigma_1\ldots$, where each $\sigma_i$ is a subset of $P$. To recognize such words, the edges of an automaton recognizing the language of $\varphi$ generally have to be labeled by symbols in $2^P$ (i.e. subsets of $P$).

Often multiple transitions are grouped by labeling edges in the automaton with boolean formulas over $P \cup \tilde{P}$, where $\tilde{P}$ is the set of negated atomic propositions. The edge label $f$ then stands for all models of $f$. In nondeterministic Büchi automata we can restrict $f$ to be a conjunction, as disjunction in the label can be modeled by introducing another transition.

Universal automata are the dual of nondeterministic automata, so to accept a word $aw, a \in \Sigma, w \in \Sigma^{\omega}$ from a state $q$, $w$ has to be accepted from all $a$-successors of $q$. Combining universal and nondeterministic branching one gets alternating automata. In universal automata for LTL formulas you can restrict the edge label to be a disjunction over $P \cup \tilde{P}$, as you can model conjunction in the label by introducing another transition.

With the right acceptance universal automata are as expressive as LTL, for example co-Büchi universal automata can recognize all $\omega$-regular languages.

Edit: I don't think this is a good answer after second thought. The reason is that grouping transitions in this way makes no sense for universal automata, unless the formulas on the labels have disjoint models.
Example:
Splitting $x \xrightarrow{a \land b} y$ into $x \xrightarrow{a} y$ and $x \xrightarrow{b} y$ adds the possibility to move to $y$ when only satisfying $a$, which was not possible before.
I don't see any natural way of having an automata with only disjunctive boolean formulas as edge labels, however you can get rid of the formulas entirely on the edge labels by just using symbols in $2^P$.


Best data structure for a queue with random reads? Well, it's not exactly a queue if it allows for random reads. This question is about a data structure which behaves like a queue for insertions and a sorted dictionary for reads.

Imagine an algorithm that maintains a list of elements so that:

It reads an element from the list based on its key.
It then inserts that element as the last element in the list.
On demand it returns all entities in the order in which they were inserted.

And I am looking for a solution that is faster than a naive implementation based on a linked list, which would have complexity O(n) for all three parameters - search, insert as the last element, and return all elements in the inserted order.

Such a data structure should probably:

Allow for a quick lookup of the key (e.g. a tree, a hashmap)
Maintain the order in which elements were inserted (e.g. a list, a queue)

A practical example is a list of agents receiving calls. When an agent is called, it's fetched from the list, and when it finishes the call, it's put at the back of the list. Therefore the agent that is first in that list is the most idle agent (waiting for a call the longest). In other words, the list would be sorted according to agent's idleness.

Another example implementation could be based on two structures, one dictionary and one array, referencing each other. The dictionary would keep the index in the array as the value and the array would keep the key as the value. Then the element would be removed from the array by looking up the value/index in the dictionary and the dictionary would be updated with the new index once the element was put as the last element in the array.

Take any dictionary data structure and link its entries in whichever order suits you. In essence, you retain the $\Theta$-costs from the basic structure.

In search trees, this is called threading. It gives you constant-time access to the first and last element, respectively, and maintaining the threading takes only constant-time overhead for each dictionary or queue operation. As a consequence, you get $\Theta(\log n)$ access by key, $O(1)$ access to front and back of the queue (without modification), and $\Theta(\log n)$ insertion and deletion.

If you use hashtables you get $O(1)$/$\Theta(n)$ (AC/WC) access by key, $O(1)$ access to front and back of the queue (without modification), and $O(1)$/$\Theta(n)$ (AC/WC) insertion and deletion. The usual caveats apply.


Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable Define the language
$\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$
where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$.
Prove that $R$ is co-recursively enumerable (co-r.e.).

So far, I have the following:
In order to prove the above, we need to show
$\qquad R^c$ =  $\{x \in \{0,1\}^\ast \mid C(x) \lt |x| \}$
is r.e. That is there exists a program $\pi$ such that the univeral TM $U$ with argument $\pi$ equals $x$ and $|\pi| \lt |x|$ (where $U(\pi) = x$ and $|\pi| \lt |x|$).
We start by enumerating all strings in $\{0,1\}^\ast$.
I have no idea where to go from this point onward.

Fancy answer

We need to show that the set
$$R = \{x \in \{0,1\}^* \mid C(x) < |x|\}$$
is c.e. (allow me to use the new terminology). The defining condition for $R$ is equivalent to
$$\exists n, m \in \mathbb{N} \,.\, T(n,0,m) \land U(m) = x \land |n| < |x| \tag{1}$$
where $T$ is Kleene's predicate and $U$ the associated output function.
In words, the formula means: there exists a code $n$ such that the $n$-th machine computes $x$ (on input $0$) and the length of $n$ is less than the length of $x$. We are done because (1) is a $\Sigma^0_1$-formula, therefore it defines a c.e. predicate.

Scholium: a $\Sigma^0_1$ formula is a formula of the form
$$\exists n \in \mathbb{N} \,.\, \phi(n, x)$$
where $\phi(n,x)$ is a decidable formula. Such a formula determines a c.e. predicate: to semidecide whether it holds for $x$, just run a loop $n = 0, 1, 2, \ldots$ and test for each $n$ whether $\phi(n,x)$ holds. If and when such an $n$ is found, terminate.

Non-fancy answer

In paralell, run all machines described by codes of length less than $|x|$ (there are around $2^{|x|}$ such machines, which is a finite number). If and when one of them stops and produces output $x$, terminate.


Is there an algorithm to find the best strategy for a game? Let,

game be the state of a 2-player, turn based game
actions game player -> [move] be a function that gets the state of a game and returns all valid moves, where a move if a function move game -> game that updates the state of the game
state game -> state returns wether a game is incomplete, won by player1 or won by player 2

Countless games such as chess and tic-tac toe can be described this ways. Is there an algorithm that, given such description, returns the optimal strategy, where strategy takes the game state as input and returns the optimal move for that turn?

Your notion of "strategy" is very ill defined. Exactly what kind of object do you want this algorithm to return? Do you want it to return another algorithm?

There is an algorithm which takes a current board state and returns the optimal move. It's called Mini-Max, you can read about it here. It basically is a depth-first search for a move that doesn't allow for a losing situation. It's called minimax because it alternates for one player minimizing the benefit for player 1 (i.e. player 2) and the other player maximizing the benefit for player 1 (i.e. player 1).

There are techniques, such as Alpha-Beta pruning, which make Minimax faster, however, it is still painfully slow. For Tic-Tac-Toe, it works. For chess, a complete run is completely infeasible. In practice, instead of doing a full search, the search is done to a specific level, and then heuristics are used to evaluate which game states are the most favorable.

So, technically, an algorithm which always returned minimax would fulfill your requirement for a strategy: you could give it a game state and it would output the possible move. However, this is far beyond the capabilities that computers will ever have: expanding the full minimax tree would probably take more memory than there are atoms in the universe.


Construct a grammar for $\{a^n(bc)^m : m,n \ge 1, m < n/2\}$ I'm new to writing languages in context-free or regular grammar, so I'm struggling how to do this one. It is a bit more complicated that simpler ones I've practiced doing. The problem is to construct a grammar for the following language:
$$\{a^n (bc)^m \in \{a, b, c\}^* \mid m, n \ge 1 \land m < n/2\}$$
An explanation of how to start and go through the language would be really helpful.

Let $n = n'+1$, $m = m'+1$. Then $m < n/2$ translates to $n'+ 1 > 2(m+1)$, i.e. $n' \geq 2m'+2$. Therefore we can write the language as
$$
\{ a^{1+2m'+2+k}(bc)^{1+m'} : m',k \geq 0 \} =
\{ a^3 a^k (a^2)^{m'} (bc)^{m'} bc : m',k \geq 0 \}.
$$
You take it from here.


Partition area using test function I am looking for an efficient algorithm that can partition an area $B \subset \mathbb{R}^2$ into disjoint subsets $B = \bigoplus_i U_i$ such that a test function is constant on each of the subsets, $f \vert_{U_i} = \mathrm{const.}$

For example, consider the following partitioning:

The indicated numbers are the return values of the test function in each cell. I want to recover the partitioning, given area error bounds, with the least number of function calls.

My current approach uses a recursive grid-based method that tests at each vertex of an intial $n \times n$ grid. If not all vertices of a grid cell have the same function value, the cell is subdivided and the process repeats. This needs many subdivisions, and the initial grid must be "fine enough".

I am curious if a specialized approach exists, and if there is a common name for this problem.

The discrete version of your problem has a close resemblance with the classical Clustering problem. In Clustering given a finite set of points you have to divide the set such that points belong to a partition (cluster) iff they have similar properties.

We consider the continuous version, i.e, your problem. Let $2\epsilon < 1$ is error bound. And, we have a bounding box of size $n*n$ which we would like to partition based on functional values.

We divide the bounding box into $n/\epsilon*n/\epsilon$ grid cells, each cell has $\epsilon$ length side. Here we apply bottom up approach where the consecutive cells having same functional values are merged together. The partitioning algorithm is as follows.

i) For each grid cell $c$, compute function values in its four corner points. Let $x$ be the function value occurring most frequently among those four values (in case of tie choose one arbitrarily). Assign $x$ as a label to $c$.

ii) Start with the left and topmost grid cell. Iterate over cells from top to bottom and in a single row from left to right. In each cell $c$ if the cell on left and above (if exists) have same labels add $c$ to the cluster (partition) correspond to those cells (merging). Else if one of the left or above cell has same label add $c$ to the cluster (partition) of that cell. Otherwise start a new cluster with $c$.

You can see that the error may occur in boundary regions (between two partitions) of the partitioning and the merging procedure will give correct partitions. But, as the boundary consists of $\epsilon$ side length boxes the error is within tolerance limit.

Time complexity is $O((\frac{n}{\epsilon})^2)$.


Why is it called 'throwing' an exception? I'm just wondering where the phrase "throwing" an exception came from. I understand "raising" an exception but I'm wondering if "throwing" has a reason or meaning behind it?

As far as I know, and Wikipedia confirms, exceptions in the software sense originated in Lisp. There's a good summary in A Pattern of Language Evolution by Gabriel and Steele. Exceptions (which were not yet called exceptions) arose from the need to specify the behavior of a program if an error occurs. One possibility is to halt the program, but this is not always helpful. Lisp implementations traditionally have had a way to enter the debugger on an error, but sometimes programmers wanted to include error handling in their program. So 1960s Lisp implementations had a way to say “do this, and if an error occurs then do that instead”. Originally errors came from primitive functions, but programmers found it convenient to deliberately trigger an error in order to skip some part of the program and jump to the error handler.
In 1972, the modern form of exception handling in Lisp appeared in MacLisp: throw and catch. The Software Preservation Group lists a lot of material on early Lisp implementations, including The MACLISP Reference Manual Revision 0 by David Moon. The primitives catch and throw are documented in §5.3 p.43.

catch is the LISP function for doing structured non-local exits. (catch x) evaluates x and returns its values, except that if during the evaluation of x (throw y) should be evaluated, catch immediately returns y without further evaluating x.
catch may also be used with a econd argument, not evaluated, which is used as a tag to distinguish between nested catches. (…)
throw is used with catch as a structured nonlocal exit mechanism.
(throw x) evaluates x and throws the value back to the most recent catch.
(throw x <tag>) throws the value of x back to the most recent catch labelled with <tag> or unlabelled.

The focus is on nonlocal control flow. It's a form of goto (an upward-only goto), which is also called a jump. The metaphor is that one part of the program throws the value to return to the exception handler, and the exception handler catches that value and returns it.
I don't know when software people started using “raise” for exceptions, or for that matter when they started calling them “exceptions”. I think both terms originated from hardware, but I don't know for sure. They were well-established by the mid-1980s, for example it's the terminology used in ML (see Monahan's thesis Data Type Proofs using Edinburgh LCF, 1984) and in Ada (defined in 1983).


Finding the Big-O and Big-Omega bounds of a program I am asked to select the bounding Big-O and Big-Omega functions of the following program:
void recursiveFunction(int n) {
    if (n < 2) {
        return;
    }

    recursiveFunction(n - 1);
    recursiveFunction(n - 2);
}

From my understanding, this is a Fibonacci sequence, and according to this article here, https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/, the tight upper bound is $1.6180^n$. Thus, I chose all the Big-O bounds >= exp(n) and all the Big-Omega bounds <= exp(n). Below are the choices:
O(1)
O(log n)
O(n)
O(n^2)
O(exp(n))

Om(1)
Om(log n)
Om(n)
Om(n^2)
Om(exp(n))

The answer choices I selected:
O(n^2)
O(exp(n))

Om(1)
Om(log n)
Om(n)
Om(n^2)
Om(exp(n))

However, it was alerted that a few of my answers were incorrect (not sure which of them). This seems strange, considering that this recursive function mimics the calls of a fibonacci sequence which has a Big-Theta exponential time complexity.

$1.6180^n$ is not an upper bound to the running time of your program, not even up to multiplicative constants (in fact it is a lower bound).
However $O(\phi^n)$ is a valid upper bound, where $\phi = \frac{1+\sqrt{5}}{2} > 1.618$ is the golden ratio. It is also easy to see that your program takes $\Omega(\phi^n)$ time, so the above upper bound is asymptotically tight.
That said, $\phi^n \not\in O(n^2)$, so that answer is incorrect.
Moreover, $\phi^n \not\in \Omega(e^n)$ since $\phi < e$, so that answer is incorrect too.
Finally, notice that your answers contradict each other since you say that the running time of the program is both in $\Omega(e^n)$ and in $O(n^2)$ but $\Omega(e^n) \cap O(n^2) = \emptyset$.


Enumerate All Possible Strings Over Alphabet I am given the following decision problem:

A program $ \Pi $ takes as input a pair of strings and outputs either $true$ or $false$.
It is guaranteed that $\Pi$ terminates on any input. Does there exist a pair ($I_1,I_2$) of strings such that $\Pi$ terminates on ($I_1,I_2$) with output value $true$?

It is clear that $\Pi$ is semi-decidable and to proof this, I am asked to give a semi-decision procedure. However, how do I enumerate all possible pairs strings? Or how do I enumerate all possbile (single) strings in general? Of course, such a program may never terminate, but that is no problem because I am only asking for semi-decidability.

EDIT2: Solution (Java)

Consider a string over $\Sigma$ to be a number written in base $|\Sigma|$ and implement a counter. Remember to include leading "zeroes": first generate all the length-1 strings, then all the length-2 ones, and so on.


Solving recurrence relation with different rules for odd and even n Assume $T(1) = 1$, and

$T(n) = 2T(n/2) + n^2$ for even $n$,
$T(n) = T(n − 1) + n$ for odd $n$.

I'm new of learning to solve recurrence problem, for 1, it seems we can apply Master Theorem directly and we got $a = 2$, $b = 2$, $d = 2$, therefore it's the case that $d > \log_b(a)$ and $T(n) = \Theta(n^2)$.
But I'm unsure for the given $n$ is even, does this effect to our final result?

Because I noticed on the second one, for odd $n$ it changed our result from $\Theta(n^2)$ to $\Theta(n)$. Suppose we have
$T(n) = T(n − 1) + n$, we can solve as summation from $0$ to $n$ such $0 + 1 + 2 + \dots + n - 1 + n = n(n+1)/2$, and hence $\Theta(n^2)$. However, if for odd $n$, I'm thinking this naively, we can just sum all odd numbers in the sequence so we have $1 + 3 + 5 + \dots + n = 2n-1$ and hence $\Theta(n)$. Is my assumption accurate?

When $n$ is odd, the recurrence can be unrolled:
$$
T(n) = T(n-1) + n = 2T\left(\frac{n-1}{2}\right) + (n-1)^2 + n.
$$
In total, we always have
$$
T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n^2).
$$
Applying the master theorem, we conclude that $T(n) = \Theta(n^2)$.


Multitape Turing machines against single tape Turing machines Introduction: I recently learned that a multi-tape Turing Machine $\text{TM}_k$  is no more "powerful" than a single tape Turing machine $\text{TM}$. The proof that  $\text{TM}_k \equiv \text{TM}$ is based on the idea that a $\text{TM}$ can simulate a $\text{TM}_k$ by using a unique character to separate the respective areas of each of the $k$ tapes.

Given this idea, how would we prove that a process taking $t(n)$ time on a $\text{TM}_k$ can be simulated by a 2-tape Turing machine $\text{TM}_2$ with $ O(t(n))\log(t(n))$ time?

Look at the original paper by Hennie and Stearns:

F.C. Hennie and R.E. Stearns, "Two-Tape Simulation of Multitape Turing Machines", Journal of the ACM (JACM), Volume 13 Issue 4, Oct. 1966, pp. 533-546

The construction is a little bit elaborate, but not extremely difficult to understand. The basic idea is to store and keep the current symbol of each tape in the same fixed column (home column) and simulate a shift of the $k$ tapes using a series of partially filled "buffers" of increasing length placed on the two tapes on the left and right side of the home column in order to avoid a full shift (that would require $O(t(n)^2)$ steps). If you need further help, modify the question and ask about the points in the paper that are not clear.


Find the appropriate product I have a number $n$ and an integer $x$ which ends on $1, 3, 7 \ or\  9$, meaning that the last digit (rightmost digit) of $x$ is one of those 4 numbers.

Now if $z = x * y$, what number do I have to choose for $y$ such that the $n$ last (rightmost) digits of $z$ are equal to $1$ (I mean the numerical value of the rightmost $n$ digits of $z$ has to be $1$) while ignoring leading zeros.

Examples:

// computes y
long computeY(int n, long x) {
    // ...magic...
    return y;
}

computeY(1, 9) == 9 (because 9*9 = 81, take the n rightmost digits, result is 1)
computeY(1, 7) == 3 (because 7*3 = 21, take the n rightmost digits, result is 1)
computeY(2, 11) == 91 (because 11*91 = 1001, take the n rightmost digits, result is 1, ignore leading zeros)
computeY(3, 17) == 353 (because 353*17 = 6001, take the n rightmost digits, result is 1, ignore leading zeros)
computeY(5, 11327) == 23263 (because 11327*23263 = 263500001, take the n rightmost digits, result is 1, ignore leading zeros)

I encountered this problem during a programming contest at my school and am stuck, It looks like I have to use number theory but I just don't know where to start.

Suppose that you are given the last $n$ digits of $x$, which is the same as knowing $x \bmod 10^n$. You want to find the last $n$ digits of $y$, that is, $y \bmod 10^n$, given that $xy \bmod 10^n = 1$. Since $xy \equiv 1 \pmod{10^n}$, the solution is $y \bmod 10^n = (x \bmod 10^n)^{-1}$, the inverse being taken in $\mathbb{Z}_{10^n}$. The condition $x \bmod 10 \in \{1,3,5,7\}$ guarantees that $(x,10^n) = 1$, and so the inverse always exists.

In order to calculate the inverse, use the extended GCD algorithm to find $a,b$ such that $a(x \bmod 10^n) + b10^n = 1$, and take $y \bmod 10^n = a \bmod 10^n$.

For example, suppose you know that $x \bmod 10^5 = 11327$. The extended GCD algorithm gives
$$
23263 \cdot 11327 - 2635 \cdot 10^5 = 1,
$$
and so $y \bmod{10^5} = 23263$.


Syntax of a Pushdown Automata transition function I just learned PDAs in class today, but am having problems understanding the syntax of the transition function. Could someone please explain to me the meaning of this syntax:

$\delta(q, \lambda, S) = \{(q, aaB), (q, bbA)\}$

This is one of the rules for my language.  I am unsure of what the meanings of this syntax exactly is.

The rule, in English, can be rendered roughly as follows:

  If the machine is in state $q$, and $S$ is the topmost stack symbol, the machine may do either of the following things without consuming any input: it may remain in state $q$ and replace $S$ with $aaB$; or it may remain in $q$ and replace $S$ with $bbA$.

A good way to think about PDAs and transitions is to reason about configurations. The configuration of a PDA consists of the following information: the state, the unread input, and the contents of the stack. Indeed, this makes the transition function (almost) a (partial) function from configurations to (sets of) configurations.

$q$ is the state;
$\lambda$ is used to indicate that the current symbol may be input symbol, and that the input should not be reduced as it normally would after a transition;
$S$ gives the topmost stack symbol, which is the only part of the stack contents the PDA can see.


What is a contiguous subarray? What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what contiguous in this actually is.

Ex: Wikipedia: Maximm subarray problem has no explanation of why the given "subarray" is contiguous or what contiguous means in the context.

This is just the ordinary dictionary definition of "contiguous": all adjacent in space. A subarray is defined by any subset of the indices of the original array; a contiguous subarray is defined by an interval of the indices: a first and last element and everything between them.


Which calculating running time are correct? Let $C$ be an array with length $n$ (assume the elements are cities with some properties). We have some properties sorted by importance. For example, 1.area, 2.population size, .... We use the following algorithm to find the best city according to sorted properties:

We choose the first property and examine each city. Then we delete half of the cities. (assume we can do this by $O(n)$ time.) Now we apply the second properties and again delete half of the remain cities. We continue this way until one city remains.

Can we say the running time is equal to $O(n)$ according to the recursive function
$T(n)= T(n/2)+ O(n)$,
and the master theorem or the running time is equal to $n \log(n)$ because we use binary search and in each iteration, we apply an operator in linear time?

which is correct and why another one is incorrect?

The $T(n)= 2 T(n/2)+O(n)$ is $\mathcal{O}(n \log(n))$

Your recursion $T(n)=T(n/2)+O(n)$ is $\mathcal{O}(n)$ by The 3rd case of The Master Theorem.


Why do we need Kleene Star when there is concatenation? For an alphabet $A = \{ a_1, a_2..., a_n \}$, the set of regular langages $L_r$ on $A$ are recursively defined by closed union, concatenation, and Kleene star's operator. I understood that languages ($A^*$) and regular languages (a subset of $A^*$) are different. Why do we need Kleene star, isn't concatenation enough for this definition?
Very simple "proof" that should be obviously wrong:
If $X \in L_r$ a regular language on $A$, and $E \in X^*$ (if i'm right also $X^* \in L_r$) a word then we could write $E$ as $e_1e_2\dots e_n = e_1 . e_2 \ldots e_{n-1} . e_n$, with each $e_i \in X$. Then $E$ is explicitly constructible by concatenation.
I forgot $\epsilon$ but so just add a simple rule that allow $\epsilon$.
My intuition says that it has something to do with infinity, that Kleene Star allows infinite-lengh chains whereas concatenation doesn't. Is it that?

Regular expressions without Kleene star define finite languages. You can prove this by induction on the structure of the regular expression. In contrast, $a^*$ is a regular expression which defines an infinite language.
We could try to define $a^*$ using concatenation and union:
$$ a^* = \epsilon + a + a^2 + a^3 + \cdots $$
Unfortunately, the required regular expression is infinite, which we do not allow (infinite expressions do make sense in some contexts, for example in infinitary logic, but not here).


Turing machine for $a^i b^j$ with $i \geq j$ I would have a brief question about how to construct a Turing machine that is accepting only this language:

$\qquad\displaystyle L_2 = \{a^i b^j \mid i \geq j \}$.

I can't come up with any mechanism that would preserve that there are greater or equal number of 'a's than 'b's. Could you suggest me something?

I concur with the Patrick87's suggestion, so here's my version of it.

For the notation in the state diagram, I've used a slightly lazy version, to hopefully reduce some the normal clutter a little.

The start state is marked with the $>$ (left side, in the middle), and I've included an explicit accept state (marked with the usual double circle and "Acc"), and an explicit reject state (marked "Rej").
The transitions are labelled $\alpha \rightarrow \beta,X$, where $\alpha$ is the symbol read from the current tape cell, $\beta$ is the (optional) symbol to write to the tape, and $X \in \{L,R,S\}$ is the direction to move the tape head - note that I've included $S$ as a "stay put" option, because it's a pain in the [expletive] if you have to move the head each time, but it doesn't really change anything.
I've also added some blue, numbered arrows to assist in the explanation below.
$\sqcup$ is the blank symbol.

Now, behold in all its glory, a Turing Machine (diagram):

Now, a couple of notes by way of explanation. Of course this is essentially Patrick87's suggestion as mentioned, so if you already get that, you don't need to read further. These correspond to the blue numbers in the image:

At each iteration of the basic loop (and in particular at the start) if the tape is blank, we move to the accept state, this corresponds to $i=j$ with the trivial case of $i=j=0$ if the tape is blank to start with.
If we see a $b$, then there must be too few $a$s, not that this also takes care of the situation where the $a$s and $b$s are out of order. This transition may make more conceptual sense after going through the main loop once, but it still applies at the start.
We read an $a$, and replace it with a blank - now we are on the hunt for either a matching $b$, or, if we've already used up all the $b$s, a blank at the end of the string of $a$s.
We also have constraints on the format of the string - all the $a$s must come before the $b$s, so to ensure this, we explicitly move past all the $a$s.
Once we've done that, if we see a blank, then there aren't any more $b$s, so we can accept (this is the $i > j$ case).
If we do see a $b$, then we'll match it with the $a$ we matched at step 3, but we want to take the last one (otherwise we would need to shuffle the string around, or use extra symbols to denote deletions that aren't blanks or something).
Once we hit the end of the string, we move back one, and take off the last $b$ (note that we had to have seen at least one $b$ to get here, so there's definitely one to remove).
Now we've matched an $a$ and a $b$, we can return to the start of the unprocessed string - just keep going until we hit a blank. Then we're in the same situation as when we started, just with two less characters in the string.


Special case of the $MST-$ Problem I am working on the following exercise:

  Consider an undirected complete graph $G(V,E)$ and positive real numbers $a_1,a_2,\ldots,a_n$. The task is to find a MST with respect to the edge weights $w_e = a_ia_j$ for each $e = \{i,j\}$. Provide an algorithm that solves this problem that is as efficient as possible.

It is safe to say that just using Kruskal's or Prim's algorithm will not be sufficient here. So we should use the special structure of $w$. I came up with the following idea:

Sort the edges in increasing order according to their edge weights. This can be done in $\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$ time.
Traverse the edges, starting from the smallest and add it to $T$ if it contains an unvisited vertex. Mark the newely visited vertices. This can be done in $\mathcal{O}(\lvert E \rvert)$ time.

But  this algorithm is not as efficient as possible for it has $\mathcal{O}(\lvert E \rvert log(\lvert E \rvert))$ time complexity. The problem here is the
procedure in step 1. Could we somehow leave it out?

Since the graph is complete, you can connect each vertex with any other vertex. Note that each vertex must be connected to the tree and hence has an incident edge in the tree.

Assuming all weights are positive, choose a vertex $v$ with the minimum weight and construct the tree from all incident edges with this vertex. The tree is hence a star graph with $v$ the center of the star.

Assuming the numbers can be negative (which is not specified in you question), then distinct two cases. the first one, all weights are negative. Hence, it turns into the case above, since  all products have to be positive.

The second case is where we have at least one negative weight and one positive weight. Let $u$ be a vertex with the maximum positive weight. Let $v$ be a vertex with negative weight with maximum absolute value among all negative weights. connect $u$ to all vertices with negative weights and $v$ to all vertices with positive weights. Be aware of not adding the edge between $u$ and $v$ twice.

Try to proof the correctness as an exercise. It should be clear using elementary math and an exchange argument.


Datalog - Single Step Operator I am currently taking a class called Logic for Computer Scientist. During the first four weeks or so now we have been studying a concept Datalog with subsections Syntax and Formal Semantics and Fixed-Point Semantics. In these weeks we have looked at several definitions atoms, ground atoms, herbrand interpretations, herbrand models, and herbrand base, and these concepts make complete since to me. We are currently looking at something called the Single Step Operator(Immediate Consequence Operator), and I am having a hard time understanding what it actually does. It appears to be in the form of a set builder notation which simply builds a set based of certain rules. This operator appears to take input and filter out some results based of the rules in the Definition of the Single Step Operator

I am looking to see if somebody can actually explain what this is doing. When it comes to understanding what the symbols mean I get it. But I can understand how exactly it affects the data being passed to it/used by it. If anybody has some guidance I would really appreciate it or any good links everything I have found on Google has the same sort of layout as what I show in the image so it doesn't offer any benefit to understanding the concept.

Thanks in advance.

It's pretty straightforward from an operational perspective.  It finds all the facts deduced by firing all the rules for exactly one round on the current database.  Typically, you'll have $I_{n+1} = I_n \cup T_P(I_n)$ so that $I_n$ is a monotonically growing database.

Concretely, say you have the following rules and facts.

p(a).
q(X) :- p(X).
r(X) :- q(X).

Then the initial database is $I_0 = \{\mathtt{p(a)}\}$.  $T_P(I_0) = \{\mathtt{q(a)}\}$, so $I_1 = \{\mathtt{p(a)}, \mathtt{q(a)}\}$.  Then $T_P(I_1) = \{\mathtt{q(a)},\mathtt{r(a)}\}$ and $I_2 = \{\mathtt{p(a)}, \mathtt{q(a)},\mathtt{r(a)}\}$.  Finally, $T_P(I_2) = \{\mathtt{q(a)},\mathtt{r(a)}\}$.  At which point $I_3 = I_2$ which would be an implementation's signal to stop.  (In my particular formulation I didn't include facts as consequences but you could do that as well.  It's not clear if your definition treats facts as rules with empty heads.)


Independent sets into which all the vertices of the graph can be split How to prove that if $G$ is an acyclic transitive digraph, then the least independent sets into which all vertices of G can be divided is equal to the size of the longest paths to $G$?

This is Mirsky's theorem, a sort of dual of Dilworth's theorem. Dilworth's theorem is a standard result in the combinatorics of posets.


Understanding how to decide whether a language for a DFA is decidable So from what I understand, if a language is recognisable then using a TM it can be accepted and halted or rejected or halted, however a language that is decidable can be accepted and always halts on rejection?

Given the language $A_{\mathrm{DFA}} = \{\langle A \rangle\mid A \text{ is a DFA and } L(A) = \{0, 1\}^∗\}$ , I want to determine if it is decidable.

What I have come up with so far is that it is a recognisable language, I don't believe it can be rejected, only accepted and halted due to the fact once the read head comes across a blank it can just accept it.  Is this the way I should be thinking?  Am I correct in thinking it is not decidable or is this not a valid way to argue the point?

What should my process of thinking be when I am trying to prove it by contradiction if it is not decidable?

Thanks in advance for any tips!

Let me rephrase the question:

  Is there an algorithm that, given a DFA, decides whether its language is $\{0,1\}^*$?

Such algorithms do exist, hence the corresponding set is decidable.

I'm not sure what your instructor means by "high level description of a Turing machine", but what they should have meant is "describe an algorithm that solves the problem". Hopefully you already know how to do that.


Is Language $ L = \{ww^{R} \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $ and $ |w|_{b} \not\equiv |w|_{c} \} $ context free? $ L = \{ww^{R}  \in \{a,b,c\}^{*} : |w|_{a} \not\equiv |w|_{b} $  and $ |w|_{b} \not\equiv |w|_{c} \} $

I would use the Ogden pumping lemma. Assumption $n < m$ where $n$ is a number from lemma. My selected word : $ a ^ {m! + m} c ^ {m! + m} b ^ {m} b ^ {m} c ^ {m! + m} a ^ {m! + m} $ where the first $ b ^ {m} $ are the distinguished characters.

It seems to me that it isn't possible to pump this word in any way possible so it isn't contex-free langauge. Have I right?

Yes, you are right that $L$ is not context-free. You have found the nice word to test the pumping lemma as well.

Intuitively we cannot recognize $L$ using a pushdown automaton as the number of $b$'s has to be used twice, once in comparing against the number of $a$'s and once in comparing against the number of $c$'s. However, that is far from a proper proof.

We can just use the standard pumping lemma for context-free language for a rigorous proof.

For the sake of contradiction, let $p>0$ be a pumping length for $L$. Consider word $t=a ^ {p!+p} c ^ {p!+p} b ^ {p} b ^ {p} c ^ {p!+p} a ^ {p!+p} $, which is basically the same word you have chosen. Let $t=uvwxy$, where $|vx|\geq 1$, $|vwx|\leq p$, and $uv^nwx^ny\in L$ for all $n\ge0$.

There are two cases.

$vwx$ contains at least one letter other than $b$.
Then $vwx$ must be completely inside either the front half of $t$ or the back half of $t$ since $|vwx|\le p$ and all $a$s and $bs$ in $t$ are at least $p$ letters away from the center. WLOG assume $vwx$ is in the back half of $t$. Let $s=uwy=uv^0wx^0y$, which is a word that starts with some number of none-$b$ letters, followed by some $b$s, followed by less number of none-$b$ letters. $s$ cannot be a palindrome.
$vwx$ contains only $b$s.
Let $vx=b^k$, where $k\le p$. Let $n=\dfrac{2p!}{k}+1$. Then let $s=uv^nwx^ny= a ^ {p!+p} c ^ {p!+p} b ^ {p!+p} b ^ {p!+p} c ^ {p!+p} a ^ {p!+p}\not\in L\,.$

In all cases, we can pump $t$ to $s\not\in L$, which contradicts that $p$ is a pumping length of $L$. This contradiction shows $L$ is not context-free.

Here are two related exercises.

Exercise 1. Show the following language is not context-free.
$$ L = \{w  \in \{a,b,c\}^{*} : |w|_{a} > |w|_{b}\text{ and } |w|_{a} > |w|_{c} \}\,. $$

Exercise 2. Show the following language is not context-free. (Hint, Ogden's lemma.)
$$ L = \{w  \in \{a,b,c\}^{*} : |w|_{a} \not=|w|_{b}\text{ and } |w|_{a} \not= |w|_{c} \}\,. $$


Can a petri net fire only one transition at a single moment? After reading several articles about petri nets, I am confused on how firing works. Can Petri net system fire only one transition out of all active (fire-able transitions) at a single moment? Or are multiple transitions allowed to fire at a single moment?

Both.

Only one transition being able to fire at a time is known as interleaving semantics. Multiple transitions firing simultaneously is known as step semantics. Some people doing concurrency theory only call the latter real concurrency, and they care deeply about the difference; I'm sure the difference has consequences, but I've worked with Petri nets and I've never run into a situation where it mattered.

In a Petri net editor I used to work on, durations could be assigned to transitions - so these "transitions" represent tasks or processes that take a certain time. Once that is possible, clearly it makes a great difference whether two of them can be firing at the same time or not. But I would say such "timed transitions" really aren't transitions; rather, they are shorthands for a transition (start), a place (executing), and another transition (termination).


How to find a lambda term to complete a function? I tried to complete this exercise but i stopped...
Defining a $ \lambda $-term M such that:
$$(<M,u>)<M,v> \: \simeq_{\beta} \: <M,u>$$

I chose $M=\lambda m \lambda a \lambda b \lambda p \,((p)m)b \:$ then i have to find a representation T of a function using M that value true if the sequence is empty and false if it's not. A sequence is defined as:
$$[]=\lambda x_0\lambda x_1 \lambda z z \\
[b]=\lambda x_0 \lambda x_1 \lambda z (z) x_b\\ [b_1 b_2]=\lambda x_0 \lambda x_1 \lambda z ((z)x_{b_1})x_{b_2} \\
.\\.
\\ .
\\ [b_1 .. b_n]= \lambda x_0 \lambda x_1 \lambda z (...((z) x_{b_1})x_{b_2}...)x_{b_n} $$
so the sequence of exercise is :
$$[01101]= \lambda x_0 \lambda x_1 \lambda z (((((z)x_0)x_1)x_1)x_0)x_1 $$
For example T need to be:
$(T)[01101] \simeq_{\beta}$ false while $ (T) []\simeq_{\beta}$ true.
I really find that difficult. How i can do that?

edit.

$true=λxλyx$
and $false=λxλyy$

We can remove the dependence on what the values stored in the sequences are by assuming that we pass "the same thing" as the first two arguments. Regardless of what $b_1, b_2, b_3$ are:

$$([b_1b_2b_3]\,x)\,x = \lambda f. ((f\,x)\,x)\,x$$

This gives you an effective way to tell the difference between an empty sequence and a non-empty sequence :

$$(([]\left<M,u\right>)\left<M,u\right>)\,(\lambda x. x) = \lambda x. x$$
$$(([b_1]\left<M,u\right>)\left<M,u\right>)\,(\lambda x. x) = \left<M,u\right>$$
$$(([b_1b_2]\left<M,u\right>)\left<M,u\right>)\,(\lambda x. x) = \left<M,u\right>$$
$$(([b_1b_2b_3]\left<M,u\right>)\left<M,u\right>)\,(\lambda x. x) = \left<M,u\right>$$

So if $s$ is a sequence, consider this:

$$((((s\left<M,u\right>) \left<M,u\right>) (\lambda x. x))\,\hbox{false}$$

What does it reduce to if $s$ is empty? What does it reduce to if it's non-empty?


Why is the running time of edit distance with memoization $O(mn)$? I understand without memoization it is going to be $O(3^{\max\,\{m,n\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with height $\max\,\{m,n\}$, m and n being lengths of two given strings.

However I am not getting why it is $O(mn)$ after memoization. Can someone please help me understand this?

I also know that, in the case of dynamic programming, the complexity will be number of distinct sub-problems we solve (because we save the solution of subproblems).

How do I calculate distinct sub-problems I am solving in Edit Distance.

P.S. I am not asking here for tabulation approach (top-down method) or explanation int the form of tabulation approach. This question on Stack Overflow contains the code of Edit Distance with memoization.

I'm assuming $n,m$ are the lengths of the input strings. The number of sub-problems are the number of different inputs to the recursive procedure edit_distance, ignoring the memo input. You can check that s1 is always a suffix of the first input string and that s2 is always a suffix of the second input string. Since there are $n+1$ suffixes of the first input string and $m+1$ suffixes of the second input strings, the total number of sub-problems is $(n+1)(m+1) = O(nm)$.

If evaluating the body of edit_distance (minus the recursive calls) took $O(1)$, then the total running time would be $O(nm)$. However, this is actually not the case. The function make_pair and the ensuing hash take $\Theta(|s_1|+|s_2|)$, which for a majority of function calls is $\Theta(n+m)$. Therefore the running time is actually $\Theta(nm(n+m))$ rather than $\Theta(nm)$. This slowdown is avoided in the dynamic programming solution, which does run in time $O(nm)$.

($\Theta(\cdot)$ is similar to $O(\cdot)$; whereas $O(\cdot)$ is only an upper bound, $\Theta(\cdot)$ is both a lower bound and an upper bound. I need to use it here since the fact that the algorithm runs in time $O(nm(n+m))$ doesn't preclude the possibility that it actually runs in time $O(nm)$; to preclude this possibility we need a lower bound on the running time.)


is $x^{100000000000}$ a "polynomial time"? per this post

  $t = x^2$ means the problem is solvable in "Polynomial" time.

per this post

  in the form

  $$a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{2}x^{2}+a_{1}x+a_{0} {
> \boldsymbol{=0}}$$

  plug in $n=100000000000$ with $a_n=1$ and $a_k=0$ for all $k \neq n$

  then we see that $x^{100000000000}$ is a polynomial

  it doesn't matter if its 2, 3, or a billion, as long as the n is a finite number

in this context, does $t = x^{100000000000}$ still mean the problem is solvable in "Polynomial" time?

Yes, $x^{100000000000}$ is a polynomial. Your first quote gives an example; your second is the definition.


How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n)) We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki
"This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n log n) time: it performs n insertions at O(log n) cost each.[a]"  we can also know if we build the heap using other methods. the big O could be better. Where should we begin if we would like to prove that the  performance, Big Omega ,of building a binary heap using recursive method is  Ω(nlog(n)), which is same as Big-O?

insert method from wiki

  To add an element to a heap we must perform an up-heap operation (also
  known as bubble-up, percolate-up, sift-up, trickle-up, swim-up,
  heapify-up, or cascade-up), by following this algorithm:

  Add the element to the bottom level of the heap. Compare the added
  element with its parent; if they are in the correct order, stop. If
  not, swap the element with its parent and return to the previous step

then we have the buildheap as

buildheap((1,1),(,))
   if n==1:
      return [(1,1)]
return insert(( ,),buildheap((1,1),...(−1,−1))

Suppose that your heap is a max-heap: a parent should be larger than its children. Consider what happens when you call buildheap with the numbers $1,\ldots,n$ in that order. Each time you add a new element to the bottom level of the heap, and the heapify procedure diffuses it all the way to the root. Since element $k$ is put at level $\Theta(\log k)$, inserting the $k$'th element takes time $\Theta(\log k)$. Overall, buildheap takes time $\Theta(\log 1 + \cdots + \log n) = \Theta(\log n!) = \Theta(n\log n)$.


Quantum computing 'amplitudes' As far as I understand, you receive an output from a quantum computer for an algorithm in the form of an amplitude, which is one of the many states your qubits may be in, however this amplitude is a complex number.

I understand that you have to square the amplitude to find the probability of finding that amplitude, but how do you convert that original amplitude into something relevant to the problem (i.e. that 3*5=15)? Is there coding within the algorithm to change the amplitude into a malleable answer?

The state of a qubit, or of a collection of qubits, is given by a state vector. However, most people would say that the output of a quantum computer is in fact the result of a measurement, which transforms the state into one which indicates a single outcome.

There are many ways to approach this, but the simplest one to describe mathematically is complete measurement in the standard basis. In this case, you transform a quantum state on $n$ qubits into an $n$-bit string.

Suppose that you have a state $|\psi\rangle \in \mathbb C^{2^n}$ on $n$ qubits, given by $$ |\psi\rangle \;=\; \sum_{x \in \{0,1\}^n} \!u_x \;|x_1 x_2 \cdots  x_n \rangle \;, \quad \text{such that } \sum\limits_{x\in\{0,1\}^n} \!|u_x|^2 = 1 .$$

In order to get a classical output from a quantum computer, one thing you can do is to perform a complete measurement in the standard basis. What this means is that we collapse the state to some single output vector $y \in \{0,1\}^n$. We get different bit-strings $y$ with different probabilities, governed by the formula
$$
 \Pr\nolimits_\psi(y) \;=\; \Bigl| \langle y | \psi \rangle \Bigr|^2
\;=\; \left|  \sum_{x \in \{0,1\}^n} \!u_x \; \langle y_1 y_2 \cdots y_n | x_1 x_2 \cdots x_n \rangle \right|^2
\;=\; \left|  u_y \right|^2 \;.
$$
The outcome is then just a random output string $y \in \{0,1\}^n$, where the probabilities are given by the non-negative real numbers $|u_y|^2$. Afterwards, you can compute with the measurement result $y \in \{0,1\}^n$ however you like, with a classical computer.

It's possible to describe performing a measurement only on a single bit, or with respect to bases other than the standard basis, but that's not really necessary to answer your question; measuring all of the qubits is certainly something you can do, and it's enough to get classical outputs from quantum computations.


Unary Turing-unrecognizable language One of my final exam questions asked me to give a Turing-unrecognizable language over an unary alphabet, which I wasn't able to complete, but I ended using the Busy Beaver function (BB(k)) which is known to be something intractable or uncomputable  so that I constructed the language as a set of strings 1^BB(k) for natural number k=1,2,... It intuitively feels like it's Turing unrecognizable but how can I prove it(if this is true)?

Suppose that you have an algorithm $f$ that decides $L=\{1^{BB(k)}\mid k \in \mathbb N\}\subseteq \{1^n\mid n\in \mathbb N\}$. Then you can build the following algorithm that computes $BB$:

// input k
n = 0
values_of_bb = []
while length(values_of_bb) < k
  if f(1^n) == 1
    values_of_bb.push(n)
    n = n + 1
return values_of_bb[k]

This will be true for all strictly increasing functions from $\mathbb N$ to $\mathbb N$: if the image is decidable, then the function is computable. You just have to enumerate potential values in increasing order and put them in a list (still in increasing order), and then the $k^\text{th}$ value is simply the $k^\text{th}$ element of this list.


LTL to GBA versus LTL to BA Let's assume that I have an LTL formula and I want to convert it to a Buchi automaton. For which fragment of LTL, GBA is more succinct and for which fragment BA has the same size as GBA.

There is no precise answer to this.

The smallest GBA for a given language is never larger than the smallest BA for a given language, simply by the fact that BAs are a special case of GBAs.
It is easy to construct a language for which smaller GBA exist. Example would be (in LTL) $\mathsf{GF}(a \wedge b) \wedge \mathsf{GF}(a \wedge \neg b) \wedge \mathsf{GF}(\neg a \wedge b) \wedge \mathsf{GF}(\neg a \wedge \neg b)$ - a four-state GBA does the trick, but the BA needs more states to encode waiting for the next event (out of $a \wedge b$, $\ldots$, $\neg a \wedge \neg b$) to happen. So whatever fragment of LTL you build, this formula will not be contained therein. But if you now take a disjunction of this property with $\mathsf{GF}(a)$ and then with  $\mathsf{GF}(\neg a)$, then the smallest BA and GBA have the same size (one state). So you cannot give a precise syntactic representation of such a fragment (without making a containment check at least PSPACE-hard).
You can, of course, build an LTL fragment for which containment of the property in the fragment guarantees that the smallest GBA will not be larger than the smallest BA. You would get such a fragment, for example, by including the next-time operator as the only temporal operator in the fragment.
In practice, it doesn't matter anyway. Due to the many different optimizations in LTL-to-BA and LTL-to-GBA tools, you cannot predict very well whether they will compute BAs that are just as small as GBAs.


Is there any proof that quantum computers are more efficient than classical computers? Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also factor integers efficiently.

Is there any actual proof quantum computers can solve some problems faster than classical computers?

Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size $N$ with high probability by querying the database only $O(\sqrt{N})$ times. Any classical solution that succeeds with high probability requires $\Omega (N)$ queries to the database.


How can we use the FPTAS for problem B to solve problem A Given an optimization problem A which is NP-complete, and can be polynomially reduced to another optimization problem B which is also NP-complete. If we use an FPTAS to solve the reduced problem B' (A $\rightarrow$ B = B'), then under what rules can the solution obtained from solving with the FPTAS be directly associated with a solution to problem A?

For example, Problem A is shortest Path problem and Problem B is knapsack Problem.

You need a stronger guarantee on the reduction, that it be approximation preserving. Not all reductions are approximation preserving. An extreme example is given by Min Vertex Cover and Max Independent Set. The complement of a vertex cover is an independent set, and so there are simple NP-hardness reductions between these problems. However, while Min Vertex Cover has a 2-approximation algorithm, Max Independent Set cannot be approximated to within $n^{1-\epsilon}$ for any $\epsilon > 0$ unless $\mathsf{P=NP}$.


encrypt with permutation ciphers I came across this question:

You are given a permutation cipher defined by the bijection t: N -> N where,

t(i) = i + 10, for i < 10,
t(i) = i - 10, for 10 <= i <= 20, and
t(i) = i, for i > 20.

Assume that the first index is 0, given a message m = 'HELLO WORLD AND THIS IS A SECRET MESSAGE', what is the ciphertext c?

Where the answer was the following:

D AND THISHELLO WORL IS A SECRET MESSAGE

but i don't get how. That's now what we get if the message is spelled out diagonally
down and up over a number of rows and then read off row-by-row.

Just apply the given permutation on the string.

Your string is : 'HELLO WORLD AND THIS IS A SECRET MESSAGE'.

Now, to apply the given permutation, we have to shift the first 10 characters rightward by 10 units, and the next 10 characters leftwards by 10 units, while leaving the rest same. Note that you also need to count the spaces.


How to represent software code for code generation / automatic programming? How to integrate procedural and declarative knowledge? I am learning about deontic logics and there I can make the following inferences: If A then there is **duty to create an entity of class C**, If B then there is **duty to assign value 5 to the attribute c.a**, if A and B then **the computation D should be executed**. I. e. those deontic logic statements contain the usual propositional variables A, B, C, but they also contain actions - pieces of procedural knowledge, like create an entity of class C and so on. The questions are:

How do I represent those actions in such manner that they can be used for the code generation/automatic programming? The simple approach can be to represent them by their content - e.g. by the code in the industrial programming language.
The goal of such reasoning is to create the syntactical tree of the program from which the source code in the industrial programming language can be read as source file. How do I represent actions that they can form the syntactical tree?

I feel that the deontic logic (formalized norms) are enough for generating software code (at least business layer - classes and their behavior), but I am struggling with the consequent end of the inference - how to represent actions/source code?

This may be seen as the more general question as well: formalized norms can be seen as the declarative knowledge and we should create reactive, procedural programs / procedural knowledge from the declarative knowledge - how to represent procedural knowledge and how to create procedural knowledge from the declarative knowledge? Are there research efforts to do this and what are keywords for this type of reasearch (so - I can find the already achieved results in Google or journal databases).

Use some form of metamodelling :

  The outputs are represented as abstract syntax trees (ASTs):

  and constructed by a decoder with a dynamically-determined modular structure paralleling the structure of the output tree.

References

Modelling homogeneous generative meta-programming
Abstract Syntax Networks for Code Generation and Semantic Parsing
Canonical Abstract Syntax Trees
Pattern Reification as the Basis for Description-Driven Systems
Metamodelling: State of the Art and Research Challenges
DSL development based on target meta-models. Using AST transformations for automating semantic analysis in a textual DSL framework
The Machine that Builds Itself:
How the Strengths of Lisp Family Languages
Facilitate Building Complex and Flexible
Bioinformatic Models
Reasoning About LLVM Code Using Codewalker
Foundations of meta-programming


Can we use Operator precedence parsing with this grammar? This Grammar:

A-->Bbab|aa

B-->b

I think we can't because basically there is no relation between terminals? like no relation between a and b! or am i missing something? and the language of this grammar has only 2 members !

can we using Operator precedence parsing with this grammar?

It's an operator grammar since no right-hand side has two consecutive non-terminals. So we then attempt to construct the precedence relations:

$$b \gtrdot b \\
b \doteq a \\
a \doteq b \\
a \doteq a
$$

There is no multiple entry, so an operator precedence parser is possible.


What is the connection between combinatorial circuits and finite state automata? The diagram on the Wikipedia page of FSA shows the hierarchy of the computational devices, in that diagram it is denoted that the finite state machines are superior to the combinatorial circuits.

Combinatorial circuits are the model of propositional logic i.e. both are equivalent, where we do a discussion about the truth values of variables and the logical connectives. Whereas the models beyond the FSA process the strings and decides the membership of a string with for some language.

If there is some connection between these two models then there must be some relation between propositional logic and regular/context-free/recursive languages.

How can we construct a corresponding FSA for a given combinatorial circuit?

You can associate with a combinatorial circuit with $n$ inputs and a single output the language consisting of the $n$-bit strings on which the circuit outputs $1$. This language is finite and so, in particular, regular. This is not particularly enlightening, however.

Combinatorial circuits have a fixed number of inputs. In contrast, finite automata get as input a word of unbounded length. The goals of circuits and automata are thus rather different – circuits attempt to solve a finite problem efficiently, whereas automata attempt to solve an infinite problem. Every finite problem can be computed by some circuit, and so the challenge is to come up with a small circuit that computes it. In contrast, not all infinite problems can be solved by a given type of automata.

The more interesting relation between circuits and automata is that of translation. Given a language $L$ of binary words, let us denote by $L_n$ its restriction to inputs of length $n$. A well-known result is the following:

  If $L$ can be solved in polynomial time, then there is a polynomial $p(n)$ so that for every $n$, the finite language $L_n$ can be computed by a circuit of size $p(n)$.

Therefore one way to show that $L$ cannot be solved in polynomial time is to show that the finite languages $L_n$ cannot be computed by polynomial size circuits.

The circuits produced by the translation alluded to above are related to each other, in the sense that they can all be generated by a program which on input $n$ outputs the circuit $C_n$ for the fragment $L_n$. Such a family of circuits is known as a uniform family of circuits. When comparing the strength of circuits and automata, the correct comparison is between uniform families of circuits and automata. For example, we can strengthen the result above to an equivalence:

  A language is in polynomial time iff its finite restrictions can be computed by a uniform family of polynomial size circuits.

Thus uniform polynomial size circuits have exactly the same power as polynomial time computation. Uniform circuits often appear in practice – a good example is circuits for doing arithmetic, from whose structure their uniformity is apparent. Non-uniform circuits – ones which cannot be produced uniformly – can have unlimited power. For example, non-uniform circuits can solve the halting problem in its unary formulation, $$\{ 1^n : \text{ the $n$th Turing machine halts on the empty tape} \}.$$

Nevertheless, it is believed that even non-uniform polynomial size circuits cannot solve NP-hard problems, a conjecture known as $\mathsf{NP} \neq \mathsf{P/poly}$. At some point in time this looked like a promising avenue for proving $\mathsf{P} \neq \mathsf{NP}$, though at the moment this point of view seems naive.


Exponential averaging for SJF CPU scheduling Calculate the exponential averaging with $T_1 = 10$, $\alpha=0.5$ and the algorithm is SJF with previous runs as $8,7,4,16$.

  9
  8
  7.5
  None

I am getting 4. None as the answer.

But it is given that 3. 7.5 is the correct answer.
I think I am missing something here.

Because I only used the formula, $S_{n + 1}{}{}{}{} = a(T_n) + (1-a)*S_n$.

A possible interpretation of the problem is that we initially had jobs with actual run times 8, 7, 4, and 16. Assuming no new jobs entered the queue, we'd schedule then in increasing order of their times, namely 4, 7, 8, 16 (since that's what SJF means--shortest job first). Under these assumptions we'd have time slices
$$\begin{align}
T_2&=\frac{1}{2}(4+10)=7&\text{after the first job has run}\\
T_3&=\frac{1}{2}(7+7)=7&\text{after the second job has run}\\
T_4&=\frac{1}{2}(8+7)=7.5&\text{after the third job has run}\\
\end{align}$$
so the fourth job would be given a slice of 7.5, which is choice (3).

This isn't an entirely satisfactory answer since of course the OS might not know how much time the jobs would actually take before hand, but if the problem assumed they'd be run in that order (4, 7, 8, 16) we'd have what was mentioned as the correct answer, so it's at least a possible interpretation.


What is the complexity of k-clique problem with a predetermined vertex in the solution? Clique (from WikiPedia):

Clique is a subset of vertices of an undirected graph such that every
two distinct vertices in the clique are adjacent; that is, its induced
subgraph is complete.

K-Clique problem: Finding a clique of size K. This is NP-complete according to Wiki,

Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

Let us consider a "constrained k-clique problem" - which is a k-clique problem with a constraint of having a predetermined vertex included in the solution. What would be the complexity of this problem? Is it a known problem in the literature?

It is still $\mathsf{NP}$-complete.
Consider the following reduction from the normal $\mathrm{Clique}$ problem:
Given a graph $G$ and some desired clique size $k$, add a new vertex $v^\ast$ which is connected to all vertices of $G$ to obtain a new graph $G^\ast$.
Then $(G^\ast, k + 1, v^\ast)$ is a yes-instance of your modified $\mathrm{Clique}$ problem if and only if $(G, k)$ is a yes-instance of $\mathrm{Clique}$.


Infinite Union of non-regular languages Is infinite union of non-regular languages $L_i$ that form a chain such that $L_i\subseteq L_{i+1}$  always non-regular?

Or is there a possibility that it be ever regular?

Is there an easy way to see this?

Let $L$ be a non-regular language over $\Sigma$, and let $w_1,w_2,\ldots$ be an enumeration of $\Sigma^*\setminus L$. Define $L_i = L \cup \{ w_j : j \geq i \}$. Each $L_i$ is non-regular (why?), $L_i \subset L_{i+1}$, and $\bigcup_i L_i = \Sigma^*$.


Project to nearest point in convex polytope Is there a reasonably efficient algorithm for the following task?

Input: a point $x \in \mathbb{R}^d$; a convex polytope $\mathcal{C} \subseteq \mathbb{R}^d$
Find: a point $y \in \mathcal{C}$ that is as close to $x$ as possible

Assume that $\mathcal{C}$ is specified by a collection of linear inequalities, that the dimension $d$ is fairly high, and "close" is measured using $L_2$ distance, i.e., we want to minimize $||x-y||_2$.  is there an efficient algorithm for this problem?

I can see how to solve this in polynomial time using linear programming if "close" were measured using $L_1$ or $L_\infty$ distance, but I'm more interested in the $L_2$ distance metric.  I keep thinking there might be some algorithm based on identifying the set of inequalities that are violated by $x$ and then doing something, but I can't quite put together a working algorithm.

I found the following paper which describes an algorithm (exponential-time in the worst case but often efficient, like the simplex method):

Philip Wolfe.  Finding the Nearest Point in a Polytope.  Mathematical Programming, vol 11, 1976, pp.128--149.

However, that paper requires $\mathcal{C}$ to be presented as a list of vertices rather than a list of inequalities, so it can't be used for my problem.  (Converting from inequalities to a set of vertices will cause an exponential blowup; typically the number of vertices is exponential in the number of inequalities.)

A quadratic program is an optimization problem where the goal is to minimize $y^T Q y + c^T y$ subject to $A y \leq b$. If $Q$ is positive definite, then this is a convex quadratic program and we can solve this problem in polynomial time using several methods, one being the ellipsoid method (originally due to Kozlov, Tarasov and Khachiyan [1]).

We can write $\|y - x\|_2^2$ as $y^Ty - 2x^Ty + x^Tx$. Thus an equivalent problem is
$$
\min_y\ (y^Ty - 2x^Ty) \text{ such that } A y\leq b.
$$
This is a convex quadratic program, since in this case $Q$ is the identity matrix, which is positive definite.

[1] The polynomial solvability of quadratic programming, USSR Computational Mathematics and Mathematical Physics, 20(5):223–228, 1980; Science Direct


Card-buying algorithm I'm trying to make an algorithm to calculate what combination of cards from what buyers I should get to get the cheapest deal. Taking the shipping costs into consideration. It's for a website called MagicCardMarket, which is kind of an Ebay for trading cards. The problem is that the site doesn't have a proper optimization tool, so I'm trying to make it myself. (I found some other site that does this, but you have to pay for it and I'm learning a lot already doing it myself.)

The first thing I do is gather a bunch of information. The most important parts being how many and what cards the buyer want. Then I gather all the articles that comply with these cards and throw away all the bad ones (those who's quality is too bad, or language is incorrect, ...) Articles are basically instances of those cards being sold, with info about their seller and cost. So now I have a list of cards, and for each card a list of articles for those cards, and for each article a cost and seller (and from this seller I can get the shipping cost, this can depend on how many cards are bought from a single seller, though most of the time it stays almost constant.)

So now I'm looking for an algorithm to get all the cards you want, as cheap as possible. Taking into consideration that when I buy from more sellers, the shipping cost will go up.

Are there any algorithms I should look at, that might lend themselves to this problem very nicely? Or perhaps some general tips for these kinds of algorithms? It's the first time I'm trying to make this kind of algorithm, so I wasn't sure what to search for either.

The easiest way would probably be to just get all possible combinations, and check which is the cheapest, though most cards will have several hundreds of articles associated with them, and most of the time you'll have 60 to 80 cards you want to buy (a full deck.) So I don't think this is a good way, it uses enormous amount of ram and takes a lot of time. I'm also writing it as a web-app, preferably something that can also work on mobile phones.

Thanks a lot!

PS. I wasn't sure if this is the proper forum to ask this, please redirect me if I was wrong.

If you want to solve this in practice, I would suggest that you formulate it as an instance of integer linear programming (ILP).

You can have a variable $x_i$ for each article that is one if we buy the $i$th article, or $0$ otherwise.  Now you get some constraints.   For instance, if I want 2 of the Dreadlord card, and they're offered in the 3rd, 7th, and 8th articles, then I get the constraint that $x_3+x_7+x_8 \ge 2$.  The objective function is your total cost.  You want to minimize your total cost, subject to the requirements.

Here's how you can model the total cost.  The only tricky bit are the shipping costs.  For simplicity, assume that the shipping cost from a seller is fixed no matter how many items you buy from that seller.  To help with modeling the shipping costs, introduce a variable $y_j$ for each seller, where $y_j=1$ if you buy anything from the $j$th seller and $y_j=0$ otherwise.  Now use the "logical OR" construction from here to relate the $y_j$'s to the $x_i$'s.  For instance, suppose that articles 4, 5, and 9 are from seller 2.  Then you add the linear inequalities $y_2 \ge x_4$, $y_2 \ge x_5$, $y_2 \ge x_9$, $y_2 \le x_4 + x_5 + x_9$, $0 \le y_2 \le 1$.  Do this for each seller.  Now, the total cost is
$$\sum_i c_i x_i + \sum_j c'_j y_j,$$
where $c_i$ is the per-item cost of the card in the $i$th article and $c'_j$ is the shipping cost of the $j$th seller.  This is the objective function that you're going to try to minimize.

Then, throw an off-the-shelf ILP solver at the resulting set of constraints.

This problem is likely to be NP-hard, so in principle there might not be any efficient solution... but in practice ILP solvers are surprisingly good, so I bet they'll give you a pretty good solution to your problem.

Possible complications and details:  If the seller has multiple copies of a card available, we need to modify the above.  You can have $x_i$ count the number of them that you buy from that seller (instead of being 0 or 1).  Also, we need to modify the construction of the $y_j$'s, as follows.  For instance, if article 5 is from seller 2, and article 5 offers up to 17 copies of the Dreadlord card, then instead of $y_2 \ge x_5$, you should use $17 y_2 \ge x_5$ (this ensures that if $x_5 \ge 1$, then $y_2$ is forced to be $1$).

If the shipping cost is not constant per seller, then you might need a more complex model of the cost.  However, here's one simple case that you can handle without difficulty.  Suppose that the shipping cost for seller 2 is \$3 plus \$0.50 per card ordered.  Then you can treat this as a fixed shipping cost of \$3 (regardless of how many cards are ordered), and increase the per-item cost of each card offered by that seller by \$0.50.  If the shipping cost is a non-linear function of the number of cards bought, then you might need something fancier: in that case, you might want to ask a follow-up question about how to model that specific nonlinear function, and specify the nonlinear fucntion.  Or, you could approximate the shipping cost by a linear function and solve the ILP problem anyway, to get something that might be close to optimal, even if your model isn't perfect.


accessing out of range physical address What happens if a CPU instruction (e.g. on ARM architecture) tries to access a physical address that is out of range. This easily could happen if the CPU is on non-virtual (non-paging) mode. This could also happen if the CPU is in paging mode and the page table maps the virtual address to a physical address that is out of range.
A physical address is out of range iff that address is not served by any of the plugged RAM chips.

Would the CPU run into an exception and invoke some interrupt service routine?
Would the CPU read/write some garbage value?

The exact response is hardware implementation specific. Typically the memory access will timeout and a hardware exception will be generated. DEC called these Machine Checks, other manufacturers may use different terms.  The CPU will follow some interrupt path that will handle the timeout.  In normal operation the most common result will be a system crash (again different terms are used, but "Bugcheck" was favored by DEC, "ABEND" is used by others.).

There are some system implementations that don't have a timeout mechanism, in these cases the typical response would be a hang waiting for a response from memory or in a less desirable case, random noise would be read from the data lines.

During boot sequences, the exception handling is sometimes changed so that the system configuration can be discovered.  The configuration code may "probe" addresses until it gets an exception in order to find the end of physical memory. Again, this is architecture dependent and not always necessary if the hardware provides some other means of determining the installed memory.

Since you mention ARM specifically, you can read a white paper for ARM memory implementation here:
Principles of ARM® Memory Maps
This paper has the following recommendation regarding memory accesses:
"Unpopulated DRAM partitions must not alias any other addresses, accesses
should return bus errors."


What does "Temporal extent" mean? I am reading Long-term Temporal Convolutions for Action Recognition and under the Section 3.1, I read this:

To investigate the impact of long-term temporal convolutions, we here study network inputs with different temporal extents.....

and then

As illustrated in Figure 2, the temporal resolution in our 60f network corresponds to 60, 30, 15, 7 and 3 frames for each of the five convolutional layers. In comparison, the temporal resolution of the 16f network is reduced more drastically to 16, 8, 4, 2 and 1 frame at each convolutional layer. We believe that preserving the temporal resolution at higher convolutional layers should enable learning more complex temporal patterns. The space-time resolution for the outputs of the fifth convolutional layers is $3 \times 3 \times 1$ and $1 \times 1 \times 3$ for the 16f and 60f networks respectively. The two networks have a similar number of parameters in the fc6 layer and the same number of parameters in all other layers. For a systematic study of networks with different input resolutions we also evaluate the effect of increased temporal resolution $t \in \{20, 40, 60, 80, 100\}$ and varying spatial resolution of $\{58 \times 58, 71 \times 71\}$ pixels.

How can we reduce temporal resolution of a ConvNet at each convolutional layer.
What does preserving the temporal resolutional mean and what does complex temporal resolution mean?
I've taken courses on Convolutional Neural Network and never heard of anything such as "temporal extent" or "temporal resolutions". Searching about them gives links to other research paper, which still use the term without describing its meaning.
Anyone, kindly put some light on it.

Temporal extent is the same as duration. It is measured in units of time, like second. For example, 1 second is a duration or temporal extent.


Finding the language generated by a context-free grammar This is a question from the Dragon book (I apologize for translation mistakes, I don´t have the English version on hand):

What language is generated by this grammar?
$S \rightarrow a S b S \mid b S a S  \mid \epsilon$

I don't know what I'm supposed to do here. The definition in the book about languages says this (and that's pretty much it in the chapter):

a language is the set of all words that can be produced by any parse
tree.

So, if I want to make "any" parse tree out of this grammar, I can recursively keep building it, using just the first two rules. I searched a bit and got the impression that every rule has to be used once, but I'm not sure. It would be very helpful if someone were able to provide some tips on solving these sorts of problems.

Hint: What can you say about the number of $a$s and $b$s in the produced words?

  It would be very helpful if someone were able to provide some tips on
  solving these sorts of problems.

There is no one-size-fits-all recipe here. It is undecidable in general, whether two CFGs produce the same language or two CFLs are the same language. A useful method is trying to notice the properties which remain invariant during the productions.


Find node that splits tree in half Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the complexity?

Can I please have a hint?

Use dynamic programming to find division number of each node, For leaf nodes set it to $0$
Then recursively for parent of each leaf node set it to sum of division of it's child, and for each child because that child is not counted in division number of itself we should add its division number by one to calculate the parent division number:
$$\text{division}(v) = \Sigma (\text{division}(\text{child}_i)+1)$$
Use above recursion structure to set division number of each node, but if in some point if you have division number bigger than equal to $|V|/2$ output this node.

This is bottom up $O(|V|)$ algorithm because you will check every node at most once, and the operation which calculates division numbers is at most $\Sigma \text{ deg}(v_i) = 2|E| = 2|V-1|$.


What is the time complexity of binary sum (recursion) Currently, I'm reading Data Structures and Algorithms in Java, 6 edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser link, particularly a chapter about recursions.

There is an example of algorithm which uses a recursion to calculate sum of all elements of the array:

public static int binarySum(int[ ] data, int low, int high) {
  if (low > high)  // zero elements in subarray
    return 0;
  else if (low == high) // one element in subarray
    return data[low];
  else {
    int mid = (low + high) / 2;
    return binarySum(data, low, mid) + binarySum(data, mid+1, high);
  }
}

It further says:

  the running time of binarySum is O(n), as there are 2n−1 method calls, each requiring constant time.

I don't understand why it is that the time complexity is O(n) and not O(logn). What am I missing here?

First of all, calculating the sum can't be better than $O(n)$ in the general case because you have to inspect all elements in order to determine the sum.

The function also does not halve the problem size every step: instead of choosing one subarray, as in binary search, we sum both subarrays. This does not save work at all.

We can determine the running time using the recurrence relation:

$$T(0) = T(1) = 1$$
$$T(n) = 2 \times T(n/2) + 1$$

Setting $k = log_2(n)$ we can write this this as:

$$T'(0) = 1$$
$$T'(k) = 2 \times T'(k-1) + 1$$

Now we can use:

$$T'(n) = \sum_{i = 1}^{k} 2^i \times 1$$
$$= 2^{k + 1} - 1 = 2 \times 2^{k} - 1$$
$$= 2 \times n - 1$$


Is a particular string regular (e.g is '010') regular? If the alphabet is $\{0,1\}$, then is the string '010' regular?

I think it is regular because DFA and regular languages are equivalent and this string has a DFA but at the same time it seems to contradict pumping lemma which implies not regular. Here is what I mean.

For pumping lemma first we have to take $w$ only in the language (here the language is just '010') So $w=$ '010'. I choose $k = 2$ then the new string $w=xy^kz$ has length more than 3 so it is definitely not '010', which means this language is not regular!

What am I missing?

Being regular is a property of languages, not of words.

However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, $\{ 010 \}$. This language, just like any other finite language, is regular.

Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.

  If $L$ is a regular language then there exists a constant $n$ such that for all words $w \in L$ of length at least $n$ there is a decomposition $w = xyz$, where $|xy| \leq n$ and $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$.

Your argument is ignoring the constant $n$, which could be larger than the length of all words in $L$.


How to show that i have significant improvements over the baselines? I had review feedbacks regarding my recent publications and reviewers argued that the improvements are not significant over the baselines.

I tried my classification algorithm on some image datasets such as Extended Yale, and in the literature (other papers) i noticed the same amount of improvements in the results was assumed good enough (e.g. only 0.20 % improvements).

So, how should i convince the reviewers that my results are good enough according to the previous works?

Odds are, you can't.  That's a judgement call, and it's notoriously hard to get other people to change their judgement.  The path is to find new evidence or facts they might not be aware of; assemble a persuasive argument; and see what happens.

But in this case, without knowing anything about the domain, I suspect the reviewers might be right.  Why would a difference in accuracy of 0.20% make a practical difference?  What new capability would it provide?  How much money would it save?  Often it's not that significant.

I see this misconception a lot.  People see another paper was accepted (to a different conference/journal), see that it had improvement of X%, assume that it was accepted because of X% improvement, and assume that if they get X% improvement their paper will/should be accepted too.  Neither of those assumptions is valid.  You don't know why that other paper was accepted.  Maybe it was accepted because the ideas it had were intriguing.  Maybe it was accepted because the paper made other contributions.  Maybe it was accepted because that conference/journal has lower standards.  Maybe it was because that kind of improvement was worth one paper being published, once, but not two.  Maybe it was because the reviewers were in a good mood that way.  Maybe it was something else.  Who knows.  And just because reviewers want to accept one paper with X% improvement on task T, doesn't mean they'll want to accept 10 papers or 100 papers with X% improvement on task T.

Don't delegate your judgement to reviewers (that other paper was accepted, so it must be good). Form your own standards of what counts as valuable work. Then, strive to make your work meet those standards.  That will enable you to articulate why your paper is significant and should be accepted, on its own merits.

This is a topic you should be discussing with your advisor/supervisor and your co-authors, as they know the work you're doing and (hopefully) know the domain area and can give you much more informed advice.


JIT, AOT, Interpretation: What are differences between them? I'm a beginner in Compilation.
My understanding is that Interpretation means Interpreter takes source program as input and produce the result of this program.(source -> Interpreter -> run on the machine) Compilation means Compiler take source program as input and the front-end translate them into intermediate representation and then the back-end treats intermediate representation as input and produce machine code as output.(source -> front-end -> IR -> back-end -> machine code -> run on the machine) However, I'm confused when I learn Java and JVM. JIT seems more complicate than compilation what I understand. And I'm find some new terminologies like AOT. What differences between these terms?

The key distinction between interpreters and compilers (AOT or JIT) is this:

Interpreter: takes a source program $P$, and runs $P$, that means affecting the world through running $P$.
Compiler: takes a source program $P$, produces a new program $P_{asm}$. When we run $P_{asm}$, it has the same (hopefully) effect on the world as $P$.

In a picture:

The advantage of compilers is that generated code is faster, because a lot of work has to be done only once (e.g. lexing, parsing, type-checking, optimisation), at compile-time, so is out of the way at runtime. And the results of this work are shared in every execution. The interpreter has to redo this work every time.

A problem of AOT compilers is that they often don't have enough information to perform aggressive optimisation. This information is only available at run-time.

A JIT compiler seeks to do better, more aggressive optimisation by executing only at run-time. However, a full compilation cycle is expensive (time-consuming), so shouldn't be carried out at run-time. How can we deal with this conundrum?

The key insight is that program execution time tends to follow the Pareto Principle: the great majority of a program’s execution time is (usually) spent running in a tiny fragment of the code. Such code is referred to as hot. Pareto’s principle tells us that (typically) a program contains some hot code. Think: innermost loops. With the information available at run-time, we can aggressively optimise such hot code, and get a massive speed-up. The rest is interpreted. Sluggishness of interpretation doesn’t matter, because it’s only a fraction of program execution time.

There is just one problem ... how do we find hot code? Remember, at compile time, the optimiser couldn’t work it out (reliably). How can we do better at run-time?
Answer: Let’s use counters!
We instrument the interpreter with counters, that increment every time a method is called, or every time we go round a loop.
Whenever these counters reach a threshold, we assume that the associated code is hot. We compile that hot code, optimise it aggressively using information available at runtime. The jump to the compiled code, and execute it to completion. When the compiled code terminates, we go back to interpretation. In a picture:

Note that the description above is a simplification, the details are more complicated.

Note also that there is no need for the first part of a JIT compiler to be interpreted. In principle, and AOT can emit code that is effectively a JIT-compiler, and the job of the interpreter (evaluation and profiling) is carried out by  ahead-of-time compiled machine code.


Is the number of shortest paths between every two vertices at most 4*n^3? In every weighted graph with $n$-vertices

with negative weights,
with $n > 10$,
a weight can't appear $n$-times in graph,

there are between every two vertices at most $4n^3$ shortest paths.

I'm trying to prove whether the statement above is true or false, however I am clueless. So far I failed to find a graph where there would be more than $4n^3$ shortest paths so I'm guessing it's true?

Consider the following graph, where we have $3\times 4+1=13$ nodes, $a1, b1, c1, a2, b2, c2, a3, b3, c3, a4, b4, c4, a5$ and $4\times4=16$ edges $a1b1, a1c1, b1a2, c1a2, \cdots, a4b4, a4c4, b4a5, c4a5$ with weights $1,1,1,1,\cdots, 4,4,4,4$ respectively.

Every path from $a1$ to $a5$ is a shortest path between them since all of them have the same weight (length). There are $2^4=16$ of them.

Consider extending this graph to a much larger graph, following the same pattern. For example, suppose we will have $100\times3+1=301$ nodes and $100\times4+1=400$ edges. Now compute how many shortest paths there are between $a1$ and $a301$.

Exercise 1. Construct a graph with the same constraint such that there are more than $4n^3$ paths of the same weight between every two vertices.


Proving SSum is NP-Complete? SSUM is the same as the Subset Sum Problem with the only additional requirement is all the numbers must be unique in the subset.

To prove it's NP complete, the verifier is quite easy to construct being the same as one for the Subset Sum except you add the additional requirement of making sure all numbers are unique.

With the reduction, I assume you can use the same reduction as before from 3SAT, I'm just figuring out a way when evaluating that reduction, to determine if two or more numbers are the same. I'm using the 3SAT reduction in Sipser with the table of columns and rows. If one needs any more information I would be happy to provide.

One way to show that SSUM is NP-hard is by reduction from SUBSET-SUM. The idea is to replace each number $n_i$ by two numbers $Mn_i + \epsilon_i$ and $\epsilon_i$, where $M$ is a "large" integer and $\epsilon_i$ is a "small" integer. By varying $\epsilon_i$ you ensure that all numbers are different. You set your target at $MT+\delta$, where $T$ is the original target and $\delta = \sum_i \epsilon_i$. Further details left to you.