Splitting a group of numbers into $k$ sorted groups I have this first task:
You have a set of numbers $S =\{ \dots \}$  of length $n$.
And a number $k$.
Both $n$ and $k$ are powers of $2$ and: $1 < k < n$
Your task is to write an algorithm (pseudo-code) that splits $S$ into $k$ sets (which have the same length each): $S_1 , S_2 , \dots, S_k$  such that all the numbers in $S_i$ are smaller than all the numbers in $S_{i+1}$ for all $1 \leq i \leq k-1$ in time complexity of $O(n \cdot k)$  (end of task 1)
The second (another question, but related to the first one) task is the same, but suggesting a faster algorithm - psuedo-code (time complexity -wise)
For example:
For $S = \{11,5,2,7,1,13,15,16 \}$ and $k = 4$ I would return (right to left):
$\{16, 15 \} , \{13, 11 \} , \{5, 7 \} , \{1, 2\}$
notice the order of the numbers inside these sets does not have to be in any particular order.
My go:
What have I not tried.. god:

I thought of doing a bucket sort.

Maybe choose a random pivot and do a select for each group.

Make $k$ empty sets of length $\frac{n}{k}$ each ("in advance") and then choose the $k$-th smaller elements each iteration.

make $k$ empty sets of length $\frac{n}{k}$ "in advance" and then putting each number in the first one, and once we come across a bigger number we move the smallest of them to the next set like this for the example above (explicit details below):

This is the algorithm I have so far (number 4):
First we have an empty $k=4$ sets of length $\frac{n}{k} = \frac{8}{4} = 2$  and then comes $11$, then $5$ :
$\{11 , 5 \}, \{ , \}, \{ , \}, \{ , \}$ and then $2$ comes but it's smaller than $5$ or $11$ so $\{11 , 5 \}, \{2 , \}, \{ , \}, \{ , \}$ then comes $7$ and it is larger than $5$ so it replaces it and moves the $5$ to the next set:
$\{11 , 7 \}, \{2 , 5\}, \{ , \}, \{ , \}$ etc...
it should work but I am not sure what is the running complexity. For each set ($k$ times) I have to run $\frac{n}{k}$ iterations (the length of each subset)
Nothing works if I understand it correctly. Nothing here gives me time complexity of $O(n \cdot k)$ ...
I did not even start thinking about the second solution.. because I can't get pass the first one..
I would appreciate your help!

Your second idea seems to be close. Here is the actual algorithm (no random pivot is required):

Find the $i{n\over k}$'th order statistic for every $1\le i\le k$. This will take $O(n)$ each time for $k$ values: $O(nk)$.
For every such $i$, put all elements with values between the $i{n\over k}$'th and the $(i+1){n\over k}$'th order statistics in the $i$'th bucket. For each $i$ it would cost $O(n)$ and there are $k$ different values for $i$, thus total of $O(nk)$.

Both steps take $O(nk)$ and therefore the entire algorithm runs in $O(nk)$ as required
Hint for the second question: think how you can combine this algorithm with a coarse version of quicksort


How do IR researchers evaluate the ranks of documents? I am developing a new IR system in a specialized context. I understand that a traditional IR system (like a search engine) should rank documents in terms of their relevance for a query. The most relevant documents should come first and the least relevant (perhaps: least relevant above some threshold) should come last.

I want to evaluate my new IR system. How do researchers evaluate document rank? How do they say that this document is more relevant than that document for some query? The most obvious thing to do would be to manually assign such labels and then check the machine against the hand labels. This seems highly subjective. Maybe there is a better way?

I've read section 15.1 Manning's Foundations of Natural Language Processing but it only talks about evaluating precision and recall -- not evaluating rank. Any suggestions on where to look on evaluating rank?

If I understand what you're trying to achieve correctly, you can use this technique discounted cumulative gain.

$$DCG_p=\sum_{i=1}^{p}{\frac{2^{rel_i}-1}{\log_2{(i+1)}}}$$

$i$ is the rank, and $p$ is the number of results that you want to evaluate. For example, if you evaluate DCG for the first 10 results, then $p=10$.

NDCG is a form of DCG that involves normalizing the result. This is useful if p differs when you compare DCG scores.
$$NDCG=\frac{DCG}{IDCG}$$ where IDCG is the ideal DCG. This is found by calculating the DCG up to $p$ under ideal conditions (all documents have a relevance of 1).

Note that neither recall nor precision are used here. Relevance and rank are the factors to compare. You still need to give the documents a relevance factor, that's unavoidable, but you don't need to establish a threshold as you would with other evaluation metrics.


Differences between basic, complex and terminological facts in a Knowledge Base using First-Order Logic I've been reading the excellent book Knowledge Representation and Reasoning by Ronald Brachman and Hector Levesque.

In the beginning of Section 3.2 "Vocabulary" of Chapter 3 "Expressing Knowledge" they state:

  In creating a KB (Knowledge Base) it is a good idea to start with the set of domain-dependent predicates and functions that provide the basis for the facts about the KB's domain.

In the same section these facts are separated in three categories:

Basic facts
Complex facts
Terminological facts

After reading the entire chapter I could not entirely understand the differences between these types of facts.

Can someone help me to understand the differences in these concepts?

In §3.2 they distinguish between the following four grammatical categories, with some examples:

Predicates: Woman, Rich, Beautiful, Bankrupt
Relations: LivesAt, HadAnAffairWith, Loves
Functions: fatherOf, bestFriendOf, ceoOf
Individual constants: maryJones, johnQSmith, tomsHouse

In the background they have first-order logic with identity, which means they allow for quantification only over individual variables. Within this machinery, in §§ 3.3–5 they introduce the three types of facts.

  Basic facts are the atomic sentences and their negations.

The atomic sentences are those sentences which are made of:

a [predicate] + an [individual]. E.g.: Woman(maryJones)
an n-ary [relation] + n [individual]s. E.g.: Loves(maryJones, tomsHouse)
an [individual] + "=" + an [individual]. E.g.: maryJones = marySmith

Note that functions applied to individual constants also denote individuals (e.g., fatherOf(maryJones) is some individual), that's why clauses (1–3) include the word 'individual' rather than 'individual constant' so as to allow also for functional expressions denoting individuals. The negations of atomic sentences are defined as follows: a sentence ¬S is a negation of an atomic sentence iff S is an atomic sentence.

  Complex facts are the basic facts closed under boolean connectives and quantifiers.

That's just a fancy way of saying that: (i) basic facts are complex facts, and (ii) if φ and ψ are complex facts, then ¬φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), and ∀xφ are also complex facts. They give the following example of a complex fact on p. 34: ∀y[Rich(y) ∧ Man(y) → Loves(y, jane)] (every rich man loves Jane).

Beware that on p. 36 they list sentences like "jane ¬= john" among complex facts, suggesting that they're not basic facts. But they are. I suspect that's why you've been having hard time seeing the difference between the types. By the definition of basic facts (see above), sentences like "jane ¬= john" are considered basic, because they're the negations of atomic sentences such as "jane = john".

  Terminological facts are complex facts taken to be axiomatically or definitionally true.

A better term for them would be "definitional facts" or "meaning postulates" (as Rudolf Carnap calls them). Consider the predicate Man. If someone is a man, we know, without having to see this person, that he is not a woman; it's definitionally true! We capture that logical relationship between predicates Man and Woman with the terminological fact: ∀x[Man(x) → ¬Woman(x)]. That is only one example of a terminological fact; more can be found on pages 36–7. They're pretty straightforward to understand.

Hope this helps clarify the distinction.


Can all NP-complete cryptosystems be broken if one is broken? I was just reading something about NP-hard problems and cryptosystems.

I was thinking: Every NP-complete problem can be reduced to another and every NP-complete problem has an equivalent (NP-hard) optimisation problem. A successful attack on one such NP-hard cryptosystem $A$ would mean that every other NP-hard cryptosystem $B$ would be vulnerable to that same attack; just reduce $B$ to $A$ and use the available attack.

That would actually mean that we would be able to extend Information Set Decoding attack of Code-based systems to any NP-hard based cryptosystem.

Is this consideration correct?

As Yuval points out, contemporary crypto systems are not based on
NP-complete problems.

NP-hardness is a worst-case notion of hardness. A problem
might be NP-hard but easy to solve in many cases, or on average,
or even in most cases. A crypto systems that was easy to crack on
average would not be useful.  We want crypto systems that are
hard to crack in almost all cases (we cannot ask for all cases
because the adversary can -- in principle -- just guess the
secret used).

This seemingly stronger notion of hardness is formalised by  one-way functions.

Incidentally, the existence of one-way functions implies $P \neq NP$,
so you can imagine that we don't know if they exist.  The reverse
implication (does $P \neq NP$ imply the existence of one-way
functions) is also an open problem.

There is an interesting theory of physical unclonable function which can be
seen as the physical analogue of a one-way function.


Retrieving the shortest path of a dynamic graph I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is dynamic? By saying dynamic I mean that we can insert or remove vertices during the execution of the program. I'm trying to find an efficient algorithm for updating the shortest paths from a vertex $v$ to every other vertex $u$, after inserting an edge $e$, without needing to run the shortest path algorithm in the new graph again. How can I do this? Thanks in advance.

Note: the changes can be done after the first iteration of the algorithm
Note[2]: two nodes are given, $s$ the source and $t$ the target. I need to find the shortest path between these nodes. When the graph is updated I only have to update $\pi(s,t)$, which is the shortest path between $s$ and $t$.
Note[3]: I'm only interested in the edge insertion case.

  A formal definition: Given a graph $G = (V,E)$. Define an update operation as 1) an insertion of an edge $e$ to $E$ or 2) a a deletion of an edge $e$ from $E$. The objective is to find efficiently the cost of all pairs shortest paths after an update operation. By efficiently, we mean at least better than executing an All-Pairs-Shortest-Path algorithm, such as Bellman-Ford algorithm, after each update operation.

Edit: Below there is a simplified version of the problem:

  A weighted graph $G(V,E)$ is given, consisting of unidirectional edges, and two critical vertices $s$ and $t$. A set $C$ of candidate bidirectional edges is also given. I have to build an edge $(u,v) \in C$ to minimize the distance from $s$ to $t$.

The problem you are asking for is a well-known algorithmic problems. It is actually still open, how hard this problem exactly is. Also you should know that there are different incarnations of this problem. In contrast what you are asking for, usually only the distances are returned, whereas you are asking for the the actual shortest paths. Notice that these paths can be already very long. Dynamic graph algorithms distinguish between edge deletions only (decremental dg algorithms), edge insertions only (incremental dg algorithms) and edge insertions and deletions (fully-dynamic dg algorithms). Thus you are interested in incremental algorithms.

The algorithms mentioned in the post of AJed, are slightly outdated. There are newer results by Thorup, see here, on page 8 for a short survey. The currently best fully-dynamic exact APSP algorithm by Thorup (for distance queries, not the path), needs $O(n^2(\log n +\log^2 (1+m/n))$ amortized update time, while supporting $O(1)$ worst case query time. Notice, that if you have $O(n\log n)$ edges, then you could just recompute from scratch with Dijkstra and Fibonacci-heaps and get the same running time as in Thorup's algorithm. So if your graphs are not to dense, I would recommend using Dijkstra.

I am not aware of any better incremental algorithm. But you should do a web search if there exist newer results for this specialized problem.


How many strings are close to a given set of strings? This question has been prompted by Efficient data structures for building a fast spell checker.
Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, i.e. $\operatorname{LD}(u,v) \geq k$ for a fixed $k \in \mathbb{N}$. Informally, $\operatorname{LD}(u,v)$ is the minimum number of deletion, insertion, substitution and (neighbour) swap operations needed to transform $u$ into $v$. It can be computed in $\Theta(|u|\cdot|v|)$ by dynamic programming. Note that $\operatorname{LD}$ is a metric, that is in particular symmetric.
The question of interest is:

Given a set $S$ of $n$ strings over $\Sigma$ with lengths at most $m$, what is the cardinality of
$\qquad \displaystyle S_k := \{ w \in \Sigma^* \mid \exists v \in S.\ \operatorname{LD}(v,w) \leq k \}$?

As even two strings of the same length have different numbers of $k$-close strings² a general formula/approach may be hard (impossible?) to find. Therefore, we might have to compute the number explicitly for every given $S$, leading us to the main question:

What is the (time) complexity of finding the cardinality of the set $\{w\}_k$ for (arbitrary) $w \in \Sigma^*$?

Note that the desired quantity is exponential in $|w|$, so explicit enumeration is not desirable. An efficient algorithm would be great.
If it helps, it can be assumed that we have indeed a (large) set $S$ of strings, that is we solve the first highlighted question.

Possible variants include using the Levenshtein distance instead.
Consider $aa$ and $ab$. The sets of $1$-close strings over $\{a,b\}$ are $\{ a, aa,ab,ba,aaa,baa,aba,aab \}$ (8 words) and $\{a,b,aa,bb,ab,ba,aab,bab,abb,aba\}$ (10 words), respectively .

See Levenshtein's paper. It contains bounds on the number strings obtained from insertion and deletion of a string. If $n$ is the length of the string and the string is binary, then the maximum number of nearest neighbors in the Levenshtein distance is $\Theta(n^2)$. It is comparatively harder to say anything about $k$-nearest neighbours, but one can get bounds. These should give you an estimate on the complexity.


Hamming code distance and error detection Suppose that data are transmitted in blocks of sizes 1000 bits. What is the maximum
error rate under which error detection and retransmission mechanism (1 parity bit per
block) is better than using Hamming code? Assume that bit errors are independent of
one another and no bit error occurs during retransmission.

This is one of the questions from Tanenbaum book.

My approach is since there are 1000 data bits so, 2^r > = r+data bits +1

r = 10 and so the number of check bits is 10. So, the length of hamming code is 1010. Till here I am able to solve. But how will I get the error rate for the retransmission error detection technique compared to hamming code.

Can anyone explain how to proceed further ?

Let's see. With parity, each block is 1001 bits long vs 1010 bit for Hamming code. So if the error rate is 0, then you economize 9 bits.

OTOH, if each second block fails, the in 50% of cases you will have to transmit a second block, in 25% of cases third block and so on. On average you have to send 2 blocks.

Now, let's go deeper. If the error rate is r, this means that each bit fails with the r probability. So, you can compute probability that there are k errors in the block.

You know that if there are 0 errors, you don't need to retransmit block, for a single error you need to retransmit parity-protected block, and for 2n errors you will got unrecoverable error.

Similarly, you can compute it for Hamming code protected block.


What can I deduce if an NP-complete problem is reducible to its complement? Let's say I have a decision problem $D$ and its complement $D'$. I know D is poly-time reducible to $D'$ (its complement). Furthermore, I know $D$ is NP-complete. What is the strongest statement I could possibly make about this kind of relationship?

If an NP-complete problem is reducible to its complement then NP=coNP (why?). Conversely, if NP=coNP then every NP-complete problem is reducible to its complement (why?).


Numerator of HRRN scheduling formula In the HRRN scheduling, priority formula is

P = (W+E)/E , where W: waiting time and E: estimated run time.

CPU finds the job that has highest priority value and does that job.

However, the formula is equivalent to P = 1 + W/E. If we just "minus 1" and make a new formula P' = W/E, the order of jobs does not change.

So the question is, why do we use P = (W+E)/E rather than P' = W/E? Is there any specific reason (like P must be greater than 1)? Or are they just using the original formula since it was made?

You can use either formula, since as you mention, the resulting algorithms are completely equivalent. The reasoning behind the standard formula $(W+E)/E$ is that it is the ratio between the expected completion time to the expected running time. Presumably when the algorithm was first suggested, the expected completion time was denoted by its own variable.


Original literature on adversary argument I want to know about the early invention/use of the adversary argument (see the lecture note by Jeff Erickson) which is a technique for establishing lower bounds of problems.

I cannot find the original papers which invented/advocated adversary argument or the first problems whose lower bounds are obtained by adversary argument. (In particular, I am quite surprised that there are no wiki pages on adversary argument.)

Do you know some original literature on adversary argument?

The oldest literature can be traced back to Andrew Yao's min-max principle, which inturns has its elder root from von Neumann's.

History of game theory is not continuous in time. At least, there was some rise and then fall in the intensity of mathematicians' attention to this theory.


Searching and inserting in $O(n)$ when $n$ is the size of the key Edit: The solution to my problem is called a trie ; according to Section 8.1 of Peter Brass book "Advanced Data Structures", for a given alphabet $A$ and a word $w$ of length $n$ on this alphabet, a trie can search $w$ in $O(n)$ and insert or delete $w$ in $O(|A| n)$. Since in my case $|A|=2$, all these operations are performed in $O(n)$. Hooray !

Context :

I am trying to put an upper bound on the worst case complexity of an algorithm. In that algorithm, I have an arbitrarily big positive integer $n$, and a map in which keys are sequences of bits of length $n$. My algorithm makes use of the INSERT and SEARCH operations in that map.
So I am searching for a data structure with the least possible worst case complexity (with respect to $n$) for INSERT and SEARCH.

My first idea was : let's assume that the map is implemented with a red-black tree. Red-black trees perform SEARCH and INSERT in $O(\log m)$ (where $m$ is the number of nodes in the tree). In the context of my algorithm, there is at most $2^n$ different keys, so insert and search should run in $O(n)$.

Problem :

Binary trees usually assume that the keys are integers, which allows to compare two keys in $O(1)$. But since $n$ is not bounded, the length of my sequences can be greater than the encoding size of integers ; then it does not seem correct to just consider that my key can simply be treated as integers and compared in $O(1)$, right?

Question:

Do there exist data structures that would allow me to insert and search in $O(n)$ (worst case) with respect to the size $n$ of the key ?

What I have for now:

1: I suppose I still can use red-black trees, but comparison between two sequences of bits of length $n$ would be $O(n)$, and then INSERT and SEARCH would become $O(n^2)$, which is not nice.

2: I have come up with a very simple kind of tree that would perform INSERT and SEARCH in $O(n)$, and I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it). My solution goes like this :

Keys are only stored in the leaves of the tree, and leaves are at distance $n$ from the root
When searching or inserting, we recursively go down from the root ; on any given non-leaf node that is at distance $i$ from the root, we look at the $i$-th bit of our key : if it is 1 then go right, if it is 0 then go left.

I did not find any data structure based on this principle, but if it exists, that would be a good solution to my problem.

I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it).

What you describe is called a trie. For practical implementation you might take more than one bit at each level (e.g. take two bits and give each node four children).

  1: I suppose I still can use red-black trees, but comparison between two sequences of bits of length $n$ would be $O(n)$, and then INSERT and SEARCH would become $O(n^2)$, which is not nice.

There is potentially room for some subtlety here. If you record for each child node the bit index at which its key differs from the parent's, can you get it down to $O(n)$? I haven't thought through the answer myself, but it seems plausible that you'd essentially get a self-balancing trie-like structure, and might be an interesting exercise to attempt.

Finally, if you expect your map to be sparsely populated (i.e. to have much fewer than $2^n$ elements) it might be worth thinking about hashing.


Runtime Complexity of Memoization I am struggling to analyze the runtime complexity of the following algorithm formally:

Given a string s and a dictionary of words dict(wordDict), add spaces in s to
construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given s = "catsanddog", dict = ["cat", "cats", "and",
"sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

The proposed algorithm:
    wordBreak(s, wordDict) {
        res; //a container used to store the final result.
        if(the length of s is zero or s is invalid) {
            just output res directly.
        }
        if(we have already encountered s before) {
            return the res that s corresponds to.
        }
        if(wordDict contains s) {
            add s to res.
        }
        (looping index from 0 to the length of s) {
            t = the substring of s starting from index to the end of s
            if(wordDict contains t) {
                temp = wordBreak(substring of s from 0 to index , wordDict);
                if(temp is not empty) {
                    (looping index j from 0 to the length of temp) {
                        cancatenate the jth element of temp with t and add it to res.
                    }
                }
            }
        }
        store the result of s to storage.
        return res;
    }
}

My analysis:
Giving the algorithm, denote the length of $s$ by n. Suppose the runtime complexity is $T(n)$, then we would have something like $T(n) = T(n - 1) + T(n - 2) + \ldots + T(0) + n + 2^{n-1} - 1$, where I add $n$ because we are looping through $s$. In the meantime we are looping through temp which is a list of results. In the worst case temp can contain $2^{n-1} - 1$ results(subdivisions coming from a string of length $n - 1$). However this does not take into consideration the effect of memoization and I do not know how to achieve that. Specifically my question are:

What is the correct time complexity analysis? My guess is that it is at least $n 2^{n-1}$ which is the time taken to create the result list but this is a wild guess without formal proof.

How does the analysis differ from the case where there is no memoization.

Memoization is related to dynamic programming in the following way.
Let $V$ be the set of all possible inputs to the function $f$. Draw an edge from $x \in V$ to $y \in V$ if the computation of $f(x)$ invokes $f(y)$. The resulting graph is a directed acyclic graph (DAG).
Now suppose that you want to compute $f(x)$. Let $V(x)$ be the set of all vertices reachable from $V(x)$. In dynamic programming, we arrange $V(x)$ in reverse topological order, and compute $f$ in that order.
As an example, consider the Fibonacci recurrence $F(n) = F(n-1) + F(n-2)$, with base cases $F(1) = 1$ and $F(0) = 0$. In this case $V$ consists of all natural numbers, the edges are $n\to n-1$ and $n \to n-2$ (for all $n \geq 2$), $V(n) = \{0,\ldots,n\}$, and reverse topological order is $0,\ldots,n$. That is, we compute $F(0),F(1),F(2),\ldots,F(n)$ in this order. Whenever compute $F(m)$, all other values of $F$ which are needed are already available.

How do we compute the complexity of a memoized function? We imagine that instead of implementing it in a recursive fashion, we use dynamic programming. This means that each recursive call now takes $O(1)$; but when running $f(x)$, we actually evaluate $f$ on all inputs in $V(x)$.

In your case, $V(x)$ consists of all prefixes of $x$. In order to evaluate the running time, you need to compute, for each $n$, the running time of your procedure $T(n)$ on inputs of length $n$, assuming that all recursive calls are $O(1)$. The final answer is then $T(0) + \cdots + T(n)$.


$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates such as follows.

For a given $i$ change $S[i]$ to either $0$ or $1$
for a given $i$ find the parity of $S[1]+S[2]+...+S[i]$.

From the top of my head, there is a solution that can support these type of queries in $O(\log n)$ time, while only using linear space and linear preprocessing time to build the data structure. The idea is to build a complete binary search tree on top of the string where the leafs correspond to individual characters of $S$ and in every internal node we store the sum of all the characters that are leafs in the sub tree defined by that node. In this way we can trivially support both of the updates in $O(\log n)$ time.

However, I found a paper proving a lower bound for this problem, stating that you can not do better than $O(\frac{\log n}{\log \log n})$ for the updates, and I also found the following paper http://link.springer.com/chapter/10.1007%2F3-540-51542-9_5, and a direct link to the pdf, giving an algorithm achieving that bound, thus being optimal.

I would like to understand this algorithm however the explanation is like 1 page, and a lot of details are missing.

So I was wondering if there is any other source on this problem, because I find it very hard to find any, or is this is the only source available?

thank you in advance

I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation.

You mentioned in your question that you can use balanced, augmented trees to speed this up. In particular, if you have a binary tree and augment each node with the parity of its left subtree, then you can do updates and lookups in time $O(\log n)$ each. That's fast, but not fast enough.

Now, consider the following generalization of your idea. Suppose that instead of using a binary tree, we use a multiway tree with branching factor $k$. We augment each key in each node with the parity of the all the subtrees preceding it (this generalizes the idea of storing the parity of the left subtree). Now, let's think about how we'd do a lookup or update in this tree. To do a lookup, we use a slightly modified version of the binary tree lookup algorithm from before: walk from the top of the tree down to the bottom, at each step accumulating the parity of the subtree purely to the left of each node. The height of the tree in this case will be $O(\log_k n)$ and we do $O(1)$ work per node, so the cost of doing a lookup will be $O(\log_k n)$.

However, with this setup, the cost of doing an update increases. In particular, if we change the parity of an element, we need to walk up from the bottom of the tree to the top, changing the stored parity of every key in every node on the path upward. There are $k$ keys per node and $O(\log_k n)$ nodes on the path upward from the leaves, so the cost of performing an operation like this will be $O(k \log_k n) = O(\frac{k}{\log k} \log n)$, which is too slow. If we could somehow eliminate this extra $k$ term, then we'd be in business.

The insight the paper has is the following. If you think about our initial problem, we had an array of size $n$ and wanted to be able to compute prefix parities. We now have a $k$-ary tree where, at each node, we need to be able to solve the prefix parity problem on arrays of size $k$ each, since each node caches information about the layers below it. In the above data structure, we solved the prefix parity problem at each node by just storing an array of the prefix parities, which means that if we need to perform an update, the cost is $O(k)$. The paper's insight is that by using a more clever data structure at each node, you can perform these updates significantly more efficiently.

In particular, the paper makes the following insight. Let's suppose that $k$ is "small," for some definition of small that we'll pick later. If you want to solve the prefix parity problem on an array of size $k$, then there are only $2^k$ different possible bit arrays of length $k$. Additionally, there are only $k$ possible lookup queries you could make on a bit array of size $k$. As a result, the number of possible combinations of an array and a query is $k 2^k$. If we pick $k$ to be small enough, we can make this quantity so small that it becomes feasible to precompute the result of every possible array and every possible query. If we do that, then we can update our data structure as follows. In each node of the $k$-way tree, rather than having each key store the parity of its left subtree, we instead store an array of $k$ bits, one for each key in the node. When we want to find the parity of all the nodes to the left of the $i$th child, we just do a lookup in a table indexed by those $k$ bits (treated as an integer) and the index $i$. Provided we can compute this table fast enough, this means that doing a prefix parity query will still take time $O(\log_k n)$, but now updates take time $O(\log_k n)$ as well because the cost of a prefix parity query on a given node will be $O(1)$.

The authors of the paper noticed that if you pick $k = \frac{\lg n}{2}$, then the number of possible queries that can be made is $\frac{\lg n}{2} 2^{\frac{\lg n}{2}} = \frac{\lg n}{2} \sqrt{n} = o(n)$. Additionally, the cost of performing any operation on the resulting tree will be $O(\log_k n) = O(\frac{\log n}{\log \frac{\lg n}{2}}) = O(\frac{\log n}{\log \log n})$. The catch is that you now need to do $o(n)$ precomputation at the start of setting up the data structure. The authors give a way to amortize this cost away by using a different data structure for the initial queries until enough work has been done to justify performing the work necessary to set up the table, though you could argue that you need to spend $O(n)$ time building up the tree in the first place and that this won't affect the overall runtime.

So, in summary, the idea is the following:

Instead of using an augmented binary tree, use an augmented $k$-ary tree.
Notice that with small $k$, all possible $k$-bit lists and queries on those lists can be precomputed.
Use this precomputed data structure at each node in the tree.
Choose $k = \frac{\lg n}{2}$ to make the tree height, and, therefore, the cost per operations, $O(\frac{\log n}{\log \log n})$.
Avoid the upfront precomputation cost by using a temporary replacement data structure in each node until the precomputation becomes worthwhile.

All in all, it's a clever data structure. Thanks for asking this question and linking it - I learned a lot in the process!

As an addendum, many of the techniques that went into this data structure are common strategies for speeding up seemingly optimal solutions. The idea of precomputing all possible queries on objects of a small size is often called the Method of Four Russians and can be seen in other data structures like the Fischer-Heun data structure for range minimum queries or the decremental algorithm for tree connectivity. Similarly, the technique of using augmented balanced multiway trees with a logarithmic branching factor comes up in other contexts, like the original deterministic data structure for dynamic graph connectivity, where such an approach is used to speed up connectivity queries from $O(\log n)$ to $O(\frac{\log n}{\log \log n})$.


Minimal basis for set of binary vectors using XOR I would be surprised if this isn't a well-studied problem, but I'm not sure what else to search for at this point: you're given a set of binary $n$-vectors $S \subset \{0,1\}^n$. The problem is to find another set of binary $n$-vectors $B \subset \{0,1\}^n$, with minimal size $|B|$, such that every vector in $S$ can be expressed by the XOR results of some subset of $B$ (so $B$ is essentially a basis for $S$ using XOR instead of addition and allowing only binary coefficients in the linear combination).

In a way, this is a form of PCA for binary vectors. While searching for literature on this problem, I came across the Discrete Basis Problem also discussed in this PhD thesis, which seems closely related. Instead of XOR it uses OR, and here $|B|$ is an additional input (and the task is it to minimise the error in representing $S$ with vectors from $B$). This problem is NP-hard. Does the same apply to the problem I've presented above, or is there an efficient solution? Any pointers to existing literature would be much appreciated.

If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear algebra, which you probably know the solution for. (One option is Gaussian elimination.)


DFA multiple accepting states to Regular expression I am trying to find the regular expression that defines this DFA, I am finding this particular case difficult since it has multiple accepting states.

If I understand this DFA correctly, it recognises:

empty strings or strings with any number of b => b*

or

a followed by any number of b => ab*
or
aa followed by any number of b => aa(b*)

So the closest I have got is b*+(a+aa)+(a+aa)b* but I know this is not correct, since it doesn't recognise strings such aabaabab.

I have been using http://ivanzuzak.info/noam/webapps/fsm_simulator/ so I can see I don't know how to make the transition back to  Q0 from Q1 or Q2 when there is a b.

I took a look to How to convert finite automata to regular expressions? but the explanations are way above my current level of understanding.

Could anybody help me finding where I'm going wrong and how could I fix it?

Many thanks in advance.

Your DFA accepts all words not containing $aaa$. Such words are built of the following "building blocks": $b,ab,aab$. Additionally, a word may end with $a,aa$. In total, we get the regular expression
$$
(b+ab+aab)^*(\epsilon+a+aa).
$$


Creating a LCG with m = 32767 I want to create a PRNG for an integer only (with a max of 32767) system and tried to use an LCG. So I've chosen as $m = 32767$ and $c = 3$ and I tried to figure out a good $a$. However for the full period I have to choose $a = 32768$ which cannot be used since the maximum is 32767.

Can anyone help me creating a "good" LCG?

Another question: Since the maximum (could be / is) 32767 I don't know how to calculate the successor because $a * y_{-1} + 3$ could become greater than 32767 and this is not allowed in the system. So should I use $a * (y_{-1} \mod ((32767+3)/a) + 3$ then?

The output of an LCG with modulus $m$ is in range $[0\dots m-1]$. Hence the choice of $m=32767$ forbids the output to be $32767$. Perhaps the OP wants $m=32768$.

We want to compute $(a\cdot x+c)\bmod m$ for known constant integers $a$ $c$ $m$ on a system restricted to integers in $[0\dots32767]$ (or is it $[-32767\dots32767]$ or $[-32768\dots32767]$, but that only makes the problem easier).

We can compute $z=(x+y)\bmod m$ on this system, assuming $0\le x<m$ and $0\le y<m$, as

if (m-x > y) z = x+y; else z = y-(m-x);   when $0<m\le32767$, or as

if (32767-x >= y) z = x+y; else z = (y-(32767-x))-1;    when $m=32768$

From this primitive, it is easy to build $(a\cdot x)\bmod m$ by an addition chain, then $(a\cdot x+c)\bmod m$.


Borrowing bioinformatic methods in other fields Have the bioinformatic methods like sequence analysis, genome annotation, comparative genomics (and many others), been applied to solve problems outside the field of bioinformatics?

Of course! The perfect example is Gusfield book. Many of string algorithms came from bioinformatics. For example, sequence analysis algorithms are used in text editors.

PS: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Dan Gusfield


What is the best algorithm to find the optimal path in reducing company's real-estate footprint? I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.
Here is the problem: A company is in the process of reducing its office space and wishes to find the path that will minimize double-rent costs during the transition period.
Constraints:

There are 200 teams in the company (team = indivisible unit). Teams are of different sizes ranging from 10 to 500 individuals.
The start and end locations for each team are given.
There are 250 office locations initially (1 per team), 150 will ultimately be removed and 100 will be added. The 100 remaining locations may see a change in occupant, and there will/can be empty locations at any time period.
The transition period is of 24 time-periods (months), however, teams do not need to move every month, and should move only when new buildings are added.
Teams may move 0, 1, 2 or 3 times during the 24 month time-span
Locations are added at different time periods. Once a building is added, monthly rent starts to be charged.
Locations which are removed have leases ending at different time periods, but leases can be terminated early for a set fee.

Cost function to minimize:
$$C = \sum_{t=0}^{24}\left (M(F_{t},F_{t-1}) + DR\left (F_{t} \right ) +T(F_{t})\right)$$
with:

$M(F_{t},F_{t-1})$ the cost of moving teams from one location to another between 2 subsequent time periods, here moving cost per team is an arbitrary constant.
$DR\left (F_{t} \right )$ the cost of double-rents for the footprint at time t.  If at time t, a team's start and end locations are available, only the rent of the team's start location is counted for computation of double rent.
$T(F_{t})$ the total of early lease termination fees at a time period.  Early lease termination fees depend on each location.

Options explored:
I have started exploring different tracks to answer this problem, namely :

Create a graph with every possible permutation at every time step and then find the shortest path using a tree search algorithm.  However, the large number of teams, locations and time periods define an immense number of permutations hence I am pretty sure I cannot list all possible trajectories.
I am thinking of using a classical Solver-type tool in Python to find optimal path, however, I fear the number of variables may be too large.

My research also led me to potential methods in the fields of Dynamic Programming, Integer Programming, Branch & Bound.
Is there a clear algorithm or manner to address this that comes to mind ?
Edit : I forgot to mention that teams may move 0, 1, 2 or 3 times during the 24 month time-span.

This kind of scheduling problem might fall within the area of operations research.
I would suggest using integer linear programming.  You can formulate this as an instance of ILP, and then solve with an off-the-shelf ILP solver (e.g., Gurobi or CPLEX).
I'll outline a way you could formulate this as an instance of ILP.  We'll let $\ell$ range over locations, $t$ over teams, and $i$ over months (time periods).  Introduce the following zero-or-one variables:

$x_{t,\ell,i}=1$ if team $t$ is at location $\ell$ during month $i$.

$s_{\ell,i}=1$ if you start renting the location $\ell$ at the start of month $i$.

$e_{\ell,i}=1$ if you terminate (end) renting the location $\ell$ at the end of month $i$.

$a_{\ell,i}=1$ if location $\ell$ is available for use during month $i$.

$m_{t,i}=1$ if team $t$ moves at the end of month $i$ to a new location.

Then all of your constraints can be expressed as linear inequalities:

$\sum_{\ell} x_{t,\ell,i}=1$: each time has a home somewhere in each month.

$x_{t,\ell,1}=1$ if $\ell$ is the starting location for team $t$; $x_{t,\ell,24}=1$ if $\ell$ is the ending location for team $t$.

$s_{\ell,1}=1$ if $\ell$ is one of the original 250 locations.  $s_{\ell,1}=0$ if $\ell$ is not one of the original 250 locations.

$a_{\ell,i} = s_{\ell,1} + \dots + s_{\ell,i} - (e_{\ell,1} + \dots + e_{\ell,i-1})$.

$x_{t,\ell,i} - m_{t,i} \le x_{t,\ell,i+1} \le x_{t,\ell,i} + m_{t,i}$.

$\sum_t x_{t,\ell,i} \le a_{\ell,i}$.

Now the cost is a sum of the moving costs (a linear function of the $m$'s), the rent costs (a linear function of the $a$'s), and the early termination fees (a linear function of the $e$'s), so the cost is a linear function of the variables.  Thus, you have an ILP instance, which you can give to an ILP solver and ask it to find the optimal solution -- or the best solution it can find within a set time bound.  You'll have about $350\times 200 \times 24$ variables, i.e., about 1.6M variables, which is large but not necessarily infeasible.


Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too Consider the operation $A(L)$:

$$A(L) = \{ w: w\in L \land w_R \notin L \}$$

where $w_R$ is the reverse of $w$.

  Prove/ Disprove: if $L$ is a CFL language so does $A(L)$.

I am almost certain there's a counter-example but I couldn't find a proper one. I'd be glad for help!

Thanks

A simple first step.

Consider any language $K \subseteq \{a,b\}^*$, and let $1,2$ be two new symbols. Let $L = 1\cdot \{a,b\}^* \cdot 2 \cup  2 \cdot  K \cdot 1$.

What if $1x2\in A(L)$?


On $SUBEXP$, $PP$ and $P/poly$ Complexity zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dtime states $DTIME(f(n))$ with $PP$ oracle is not in $P/Poly$ if $f(n)$ is superpolynomial.

We know $SUBEXP=\cap_{\epsilon>0}DTIME(2^{n^\epsilon})\not\subseteq DTIME(p(n))$ for any polynomial $p(n)$.

So do we have $SUBEXP^{PP}\not\subseteq P/Poly$? So can we say either $SUBEXP\not\subseteq P/Poly$ or ${PP}\not\subseteq P/Poly$ holds?

I am trying to understand if $C^O\not\subseteq D$ for classes $C,O,D$ then does it follow either $C\not\subseteq D$ or $O\not\subseteq D$?

In other words if we have two classes $C,O$ with $C\subseteq D$ and $O\subseteq D$ then does it mean $C^O\subseteq D$?

If $D$ is low for itself ($D^D = D$) then $C,O \subseteq D$ should imply $C^O \subseteq D$, though it might depend on the exact definition of the oracle model (for resource-restricted classes there are sometimes delicate issues there). In contrast, if $D$ isn't low for itself then taking $C=O=D$ we get a counterexample.


How does insertion work in an AVL tree? From the above image, while trying to maintain an AVL tree data structure, how would the tree look after inserting the value 10? Also, if anyone has any suggestions or simple method of rotating, feel free to share. I am a bit lost with this idea of maintaining a certain height in this data structure.

AVL trees should be binary search trees. In the example you gave, 2 is the right child of 3. That isn't right since 2 < 3. Assume the 2 and 3 are switched, which results in a correct binary tree.

Remember the rule for AVL trees: for any node, the height difference between the left child and right child is at most 1. Following the tree down, the 10 is inserted as the right child of 9. This breaks the rule. Look at the subtree rooted at 6. The height of the left child is 0 while the height of the right child is 2. The tree must be rotated, which is the tricky part. 8 becomes the right child of 4. 6 becomes the left child of 8. 7 becomes the right child of 6. After all of that, the final AVL tree would look like this:

(courtesy of Uottawa).
I always visualized rotations like this:

With your left hand, "hold" the 6 and "detach" it from the 4.
With your right hand, "hold" the 8.
"Drop" the 6 so that it swings counterclockwise, due to gravity of course. (6 is now the left child of 8)
The 6 "hits" the 7. (7 is now the right child of 6)
"Attach" this whole subtree (now rooted at 8, since the 6 "fell")
back onto the 4.


Description of shape in a vector form I would like to ask for references to algorithms that can project shape information about an object to 1 dimension. Specifically I am training a neural network to be able to identify objects with similar shape as the ones in the training set. The objects in my case are molecules for which the positions, masses and radii of the atoms are known. So far I have used information about the interatomic distances.  The shape of the molecule is characterized by the distributions of atomic distances to four strategic reference locations. In turn, each of these distributions is described through its first three moments. In this way, each molecule has associated a vector of 12 shape descriptors. E.g.

shape = [5.263145206201491,
 2.374050283937628,
 0.5667128412399703,
 -0.9294169868091768,
 5.248610806623028,
 2.540858433874688,
 0.6060854720036649,
 -0.8149532304046945,
 10.186033275946016,
 5.224912272773887,
 -0.5637327938909833,
 -1.1097296046204561]

However, a 12-element feature vector is too small to describe accurately the molecular shape. I tried to add more reference location and consequently more atomic distances but I noticed no gains in accuracy. Is anyone aware of any other algorithm that can express the molecular shape in a feature vector form? Please point me to references if you know.

There's lots of work in the computer vision community on "shape descriptors".  This might or might not be useful.  See e.g., https://en.wikipedia.org/wiki/Shape_analysis_(digital_geometry), https://en.wikipedia.org/wiki/Shape_context, https://en.wikipedia.org/wiki/Image_moment, https://en.wikipedia.org/wiki/Spectral_shape_analysis.


What makes data flow analysis higher level than control flow analysis? I feel understanding why data flow is higher level than control flow is key to writing good code (and convincing others during code reviews). I find this repeatedly when arguing why my functional style programming with immutability is superior to their mutable state code which is more common and expected.

But I don't understand why one is higher level than the other. The closest I can come up with, informally, is that ultimately end users don't care about what movement of control occurred. But they DO care what movement of data took place.

Other examples

applications which just do processing last only a couple of years, whereas files which store data can last decades)
a CPU just transforms volatile data, whereas disks store data persistently

In other words, control flow is a means of achieving data flow.

Is there a more rigorous way to explain this?

(source: slideplayer.com)

Look at Wikipedia article "Control Flow". It contains typical flow chart. Arcs are the ways where control token moves from one node to another.

Now imagine you want to employ parallelism and launch several control tokens. Immediately a problem arise: how to isolate pieces of data from simultaneous modification by different control tokens. To tackle with this problem, we divide our data in parts - one parts belong to dedicated control token, and others are  for exchanging information between control tokens. The result is a dataflow diagram (or chart). That is, to manage data in parallel environment, we have to split data into pieces and explicitly manipulate them. Data flow is no more than parallel control flow.

Functional programming is another story. While there exist both control flow (von Neumann) and data flow processors, there is no functional processor. Functional programs can be compiled both to data and control flow processors. But since ordinary imperative programs cannot be directly compiled to dataflow processors (they first have to be converted to dataflow programs, which is hard), and converting functional programs to dataflow representation is easy, we can consider functional programming as a variant of dataflow programming.

And finally, consider distributed computing. Since it involves multiple computers with no shared memory, it is best described as dataflow computing and not as imperative computing. What happens inside computer nodes, is it functional programming or imperative, does not matter. But the way how data are exchanged matters. And using functional data structures to exchange data between nodes is very appropriate.


What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero? Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero one at a time what will be minimum number of operations (i.e multiplications) I will need. For example, for the matrix

$\begin{pmatrix}
    0 & 1 & 0 \\
    0 & 0 & 0 \\
    1 & 0 & 1
  \end{pmatrix}$

the answer is two. For this example

$\begin{pmatrix}
    1 & 1 & 1 \\
    0 & 0 & 1 \\
    0 & 0 & 1
  \end{pmatrix}$

the answer is two not three.

Any help to go for head start is appreciated.

Hint: Reduce to bipartite vertex cover, which can be solved efficiently.


Multi- Knapsack problem variation I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each having a weight and volume capacity, where these items need to go inside. A feature that I am looking for is that the value property of each item which depends on which knapsack it goes into. For instance, item 1 has value of v1 if goes into knapsack 1, and v2 if it goes to knapsack 2.

How can I model the problem as a knapsack and an optimization problem so to maximize the overall value? So far I came into a multiple knapsack problem, 2 dimensional. For for the value, I don't have any clue.

The simplest approach is to formulate this  as an instance of integer lienar programming.  You have zero-or-one variables $x_{i,j}$, where $x_{i,j}=1$ means that item $i$ is placed into knapsack $j$.  Then all of your constraints can be straightforwardly expressed as linear inequalities on these variables.


Calculating decimal digits of pi, using something similar to a Bailey–Borwein–Plouffe formula I have tried to Use the Bailey–Borwein–Plouffe formula to calculate pi to 3 digits as a test trial, and recieved the digit 4, which is technically correct, as 4 is the 3rd digit of pi in base 16. I would like to get the digit in decimal, as that is the current standard for numbering things in most places, as you don's see many things labelled D5 except in excel spreadsheets. Basically, I need to conduct a Bailey–Borwein–Plouffe formula from 0-6 (intead of 0 - infinity as i only need pi to 6 digits), but in decimal.

Here is what I had for the base 16 computation.

double pi2 = 0;
int n = 0;
while (n < 3)
{
    double a = (1/(Math.pow(16, n)));
    double b = (4/((8*n) + 1));
    double c = (2/((8*n) + 4));
    double d = (1/((8*n) + 5));
    double e = (1/((8*n) + 6));
    pi2 += a*( b - c - d - e );
    n++;
}

The Bailey–Borwein–Plouffe formula only works in hexadecimal. There might be other formulas for other bases, but I'm not aware of a decimal-based formula. If you want to obtain the $N$th decimal digit, you have to compute enough hexadecimal digits, there are no shortcuts.


How does this answer for automata and Hamming distance not lead to inconsistencies? I had already been given the answer by the TA in class, but I don't understand it. I'm not asking for the answer on a homework problem or anything.

The problem:

The Hamming distance ("distance") of a word w to v of the same size is the number of positions wherein they differ. The distance between a w and L is the smallest such distance from a word chosen among L.

Let k be a natural number, and L a regular language. L' is the set of words w at a distance not greater than k from L. Show that L' is regular.

The way to go about this was to construct an automaton for such an L', and to do induction on k. If k = 0, then L' = L0 = L, and M0 = (Q0, E, delta0, q0, F0).

In general

Q is the set of states for an automaton accepting words with a distance at most k.
E is the alphabet among all machines and languages.
d is the tranisition function of Mk,
q0 is the start state for Mk
F is the set of final states for Mk.

The answer, according to the TA:

Assuming that the construction is valid for all i <= k, we can form M' as follows:

Q' = Q x {0, 1}, and **q'** is an element of Q'

q0' = (q0, 0)

d'((q, 0), a) = {(d(q, a), 0)} u {(d(q, b), 1) | b element of E}

d'((q, 1), a) = {(d(q, a), 1)}

F' = {q' = (q, t) | t = 0 or t = 1}

I really don't get this. To me, it seems that if I start off with less than k+1 errors then I'll be in a state (q1, 0) for some q1, and if I read 1 error then I'm put in a state (q2, 1) for some q2. If I am in a state (q1, 1) for some q1 and read anything, then I'll be in a state (q2, 1) for some q2.

If I start with reading the first letter of any input, then I start in (q0, 0), and if I read one error then I'm in (q1, 1), and if I read 50 errors then I'm in (q, 1) for some q, but if we wanted k to be, say, 5, then I've surpassed that.

I'm really confused here. I'd appreciate any help.

Thank you.

Consider the case where $k=1$. In other words, we're allowing a single error. We take our base automaton and apply this "error-allowing transformation" to it.

The transformed automaton generally works as follows:

The state $(q, 0)$ means "the underlying automaton is in state $q$, and we haven't made an error yet".
The state $(q, 1)$ means "the underlying automaton is in state $q$, and we have made a single error".
From any state $(q, 0)$, we can make the "correct" transition, or make any "incorrect" transition (a transition meant for any other symbol) and change the $0$ to a $1$.
From any state $(q, 1)$, we can only make the "correct" transition. In other words, once we've made one mistake, we can't make any more!
If we reach either $(a, 0)$ or $(a, 1)$, where $a$ is an accepting state, then we accept.

Hopefully this makes sense; let me know in the comments if it doesn't.

Now the key is, this works for any base automaton. So if we want $k=2$, we can just apply this transformation once, and then apply the transformation again!

The states now look like $((q, 0), 0)$. If we reach the state $((a, 1), 1)$, then we've made exactly two errors. And once we've made exactly two errors (there are no more zeroes to turn into ones), we're not allowed to make any more errors, we have to follow the base automaton exactly.

And then you can apply the transformation again for $k=3$, and again for $k=4$, and so on, for any natural $k$. Induction! QED.

(Another way to prove it is to allow errors in every state $(q, \psi)$ as long as $\psi < k$. This way doesn't involve induction, and might be a bit easier to grasp, since you have a straightforward "error counter".)


Like transitive reduction, but removing vertices rather than edges? Suppose I have a directed graph $G = (V, E)$ (or, which is the same, a relation on the set $V$ as defined by the adjacency matrix) that may contain three vertices $x, y, z$, such that $xy, xz, yz \in E$ — that is to say, the relation restricted to $x, y, z$ is transitive, there is a triangle. Let us call this situation a "local transitivity". My goal is to obtain all the subgraphs of $G$ induced by cutting middle vertices from local transitivities until none remain, which I dub "resolution".

There may be multiple solutions. For instance, consider a graph given by this relation:

  a b c d
a □ ■ ■ □
b □ □ ■ ■
c □ □ □ ■
d □ □ □ □

(It looks like a square with one diagonal.)

There are two ways it can be resolved:

  a b d        a c d
a □ ■ □      a □ ■ □
b □ □ ■      c □ □ ■
d □ □ □      d □ □ □

One way I can compute the resolutions of a graph is by giving a "non-deterministic" function $f :G \rightarrow \{G\}$ that removes any single local transitivity. Repeatedly applying $f$ to any graph, I will eventually converge to a set of induced subgraphs completely devoid of local transitivities.

One way to define $f$ is by considering all the triples of distinct vertices and checking them for local transitivity. From each matching triple, the middle vertex is extracted, and any of these vertices is cut. But there is about $|V|^3$ such triples.

Is there a better way? Is there prior art that I may study?

P.S. Answering to questions from the comments:

  Is "local transitivity" the same as a triangle? Or could it (for instance) involve more than 3 vertices?

In the case I have in mind, it is specifically triangles that I need to remove. But I can see how a generalization may be offered where, given two paths $p_1, p_2: a \dots b$ such that $|p_1| \leq n$ and $|p_2| \leq m$ (counting edges), we can remove the longer. My specific problem is then the special case with $n = 1, m = 2$.

  In your example, I think there are more than two ways it can be resolved. For example, you could remove vertex a (from the abc triangle) ...

I was thinking that it is only allowed to remove a midpoint from a triangle, so that "initial" and "terminal" vertices cannot be removed, and therefore the length of the shortest path is preserved.

  What's your question? Is your question "can I enumerate all triangles faster than $O(|V|^3)$ time?" Is your question "how efficiently can I find all possible triangle-free subgraphs?"

This and that too. Primarily, I need the triangle-free induced subgraphs. Enumerating triangles is only a means to this end, but it may be a useful technique for other algorithms, elsewhere, so would be good to know.

There's a $O(n^\omega)$-time algorithm that outputs a count, for each vertex, of the number of triangles that include that vertex.  Here $O(n^\omega)$ is the running time for matrix multiplication.  See, e.g., Number of triangles in an undirected graph, Is it a valid graph canonical form?, https://cstheory.stackexchange.com/q/9972/5038.  This may or may not be faster in practice.

To enumerate a list of all such triangles can take $\Theta(n^3)$ time in the worst case, for instance, in the case where you have a complete graph on $n$ vertices, as then you have $\Theta(n^3)$ triangles in the graph, so just outputting them takes $\Theta(n^3)$ time.


Is there a reasonable algorithm to generate a certain "independent clique graph" with minimal vertices? In the process of trying to find a solution to the rat and poison puzzle with two rats, I've found myself needing the solve the following problem, in polynomial time:

Given any $k_0, k_1, k_2,..., k_{n-1} \in [2,\infty)$, we want to produce a simple graph $G = (V, E)$ and some $c_0, c_1, c_2,..., c_{n-1} \subseteq V$ such that:

Each set of vertices $c_i$ is a clique of size $k_i$ in $G$
For all $(u, v) \in E$, there exists exactly one $c_i$ such that $u, v \in c_i$
$|V|$ is minimal.

This essentially means that we want a graph with at least $n$ cliques, each of size $k_i$, such that each edge is in exactly one of these cliques, and we want the smallest such graph. Extra cliques that aren't represented by a $c_i$ will still occur but don't count as overlap, so $G$ isn't generally a block graph.

My initial thought was the following framework for an algorithm:

let c = empty array of size n
let G = ({}, {})
for i in [0, n):
    while there's not an independent set of size k_i in G:
        add a new vertex to G
    let S = an independent set of size k_i in G:
    connect every vertex in S to every other vertex in S in G
    let c[i] = S

The glaring issue is that I'm relying on a algorithm for independent set here, and there's no general polynomial-time algorithm for it. What I'm trying to figure out is if there is some structure inherent to this problem that makes independent set feasible to compute.

There's a polynomial time algorithm for finding an independent set on a chordal graph (though I can't find a straightforward presentation of the algorithm anywhere yet), so if I can prove that $G$ is always a chordal graph I've solved the problem.

A graph is chordal iff it has a perfect elimination ordering, an ordering of the vertices such that for any vertex v, v and the neighbors of v that occur later in the ordering form a clique. I'll prove this using induction.

Base case:
Our starting graph has a trivial empty ordering, so our base case holds.

Inductive step:
We need to show that adding some number of vertices, then filling out an independent set they are part of into a clique, creates a new graph with an ordering if the original graph already had one.

Let $s$ be the previous ordering (for example, $1342$). Let $t$ be an arbitrary ordering on the new vertices. Let our new ordering be $ts$, the concatenation of the two orderings. Since the only edges these new vertices have are within the new clique, and removing any of the vertices in a clique leaves the remaining vertices in a clique as well, as we move across $t$ and check if it forms a clique with the following neighbors in $ts$, it always will. Since we already know the vertices in $s$ satisfy the ordering criteria by the induction hypothesis, all the vertices in $ts$ satisfy the induction hypothesis and our new graph has a perfect elimination ordering. So the inductive step holds

So by our base case and inductive step, on every step of the algorithm, finding the independent set will take only polynomial time in the total number of nodes and edges, and since adding a $k_i$-clique can always be done in $k_i$ or fewer new vertices, the number of vertices is at most $\sum_{i=0}^{n-1} k_i$, the number of edges is at most the square of that, and therefore the whole algorithm is polynomial in the sum of the inputs, as desired.

I haven't proved that the result has the minimal number of vertices yet. That's going to have to wait for another day though. Might have to explain the previous parts a bit better too.


Metaprogramming taken to an unnecessarily high level- how can a program write not just other programs, but a programming language? So basically, automated language-oriented programming. I've tried finding info on this concept, but have had some trouble, probably because my brain is having a bit of trouble grasping the subject while thinking about it. It could be better defined as metaprogramming going to a deeper level- rewriting the programming language it is written in as well as or instead of the program itself.

Theoretically, through this a program would be able to operate on an infinite number of levels. I think this should be a key part of artificial intelligence, as we humans have written numerous programming languages all on top of each other and from scratch, so our programs should be able to as well.

How or why someone would ever do this is not the question. The better question is, "why not?"

If you are able to answer this question, don't worry because I have more to back it up. What programming languages would be best for this kind of thing, and what are some terms I can use in the future to better describe and grasp this concept?

Of course we could in principle auto-generate a full programming language. First we'd have to say what being a full programming language actually entails. Here is my attempt:

Syntax of programs.
A notion of value (programs that have no further reductions, but are not stuck).
A reduction relation giving the operational semantic.
A notion of program equality.

All of this can be specified syntactically and generated by a computer. There are tools for part of this purpose, e.g. Ott, but specifying the whole operational semantics of a realistic PL is extremely hard work. One could argue that for example the C used in programming the Linux kernel is only specified by the official GCC version used for compilation of the kernel.

As specifying all of this is such a pain, nobody has so far produced a full-spectrum meta-programming tool. At this point it is not clear how it would look like and how it would help.


Is a subgraph of G always connected I am trying to figure out if given a connect graph with N nodes and A edges, its subgraphs are connected.

In order word: given a graph G, can I have a subgraph of G that is not connected?
Or: can a subpgraph of G not be connected?

I think the answer is no because otherwise G' is not a (sub)graph.

A subgraph of a graph $G$ is any graph that has a subset of $G$'s vertices and a subset of its edges.  In particular, for an graph $G=(V,E)$, the graph $(V,\emptyset)$ is a subgraph that's not connected.


Approximating the set of witnesses of a BPP algorithm Let $\mathcal{A}$ be a randomized algorithm that decides a language $\mathcal{L}$. For each input $x\in\mathcal{L}$, we define the set of witnesses of $x$ as $W(\mathcal{A},x) = \{r\in\{0,1\}^n:\mathcal{A}(x,r) \text{ accepts}\}$. Suppose that $\mathcal{A}$ is a $\mathsf{BPP}$ algorithm.  We wish to show that there exists an algorithm $\mathcal{A}'$ also deciding $\mathcal{L}$ such that
$$
|W(\mathcal{A}',x)| \geq \frac{2^n}{4}, \qquad \text{and} \qquad
\big|\{0,1\}^n - W(\mathcal{A}', x)\big| \geq \frac{2^n}{4}
$$
for all input $x\in\mathcal{L}$.

I am sincerely lost for this problem. An idea that was vaguely suggested to me was to flip two fair coins and proceed based on the result: trivially accept if the result is $(1,1)$, trivially reject if it's $(0,0)$ and run the $\mathsf{BPP}$ algorithm for the other two remaining cases. However, I am not sure how exactly that could be of any help, of if another way can be found.

Any help would be appreciated.

The idea suggested to you was helpful.  It basically amounts to suggesting a candidate algorithm $\mathcal{A}'$.

Your next step is to try bounding $|W(\mathcal{A}',x)|$  and $|\{0,1\}^n - W(\mathcal{A}',x)|$ for that choice of $\mathcal{A}'$.  See what you can come up with.  See if you can relate $|W(\mathcal{A}',x)|$ to $|W(\mathcal{A},x)|$ etc.


Reachability matrix in time $O(|V| \cdot |E|)$ Suppose that we are given a directed graph and we want to find out if a vertex $j$ is reachable from another vertex $i$ for all vertex pairs $(i, j)$ in the given graph.
Reachable mean that there is a path from vertex $i$ to $j$.
The reachability matrix is called transitive closure of a graph.

I want to write an algorithm that rus in time $O(|V| \cdot |E|)$ and calculates the transitive closure of a directed graph $G=(V,E)$.

I have tried the following:

 Transitive_Closure(G)
         for v=1 to |V|
               for u=1 to |V|
                        T(v,u)=0
         for v=1 to |V|
                for each u in Adj[v]
                        T(v,u)=1
                        for each w in Adj[u]
                                T(v,w)=1

But isn't the time complexity $O(|V| \cdot |E|^2)$? Or am I wrong?

This algorithm definitely finds the transition matrix, but it's even in $\Omega(|V|^3)$:

    Transitive_Closure(G)
      for i = 1 to |V|
          for j = 1 to |V|
              T[i,j]=A[i,j] // A is the adjacency matrix of G
      for k = 1 to |V|
          for i = 1 to |V|
              for j = 1 to |V|
                  T[i,j]=T[i,j] OR (T[i,k] AND T[k,j])

EDIT: Is the following algorithm right?

Transitive_Closure(G)
1.  for each vertex u in G.V
2.       for each vertex v in G.V
3.            T[u,v]=0
4.   for each vertex u in G.V
5.        BFS(G,u)
6.   return T

BFS(G,s)
1.  for each vertex u in G.V-{s}
2.       color[u]=WHITE
3.       d[u]=inf
4.       pi[u]=NIL
5.  color[s]=GRAY
6.  d[s]=0
7.  pi[s]=NIL
8.  Q=empty set
7.  ENQUEUE(Q,s)
8.  while Q!= empty set
9.          u=DEQUEUE(Q)
10.        for each v in G.Adj[u]
11.             if color[v]==WHITE
12.                color[v]=GRAY
13.                d[v]=d[u]+1
14.                pi[v]=u
17.                ENQUEUE(Q,v)
18.        color[u]=BLACK
19.        T[s,u]=1

This algorithm doesn't work. Consider a graph with four vertices 1,2,3,4 and edges $1\to2\to3\to4$. Your algorithm outputs $T(1,4)=0$ even though 4 is reachable from 1.

The running time analysis of the algorithm can be improved to $O(VE)$. The first loop takes time $O(V^2)$. The number of pairs $(v,u)$ in the second loop is the number of edges $E$, and for each pair $(v,u)$, the maximal number of $w$s is $V$. So the second loop runs in time $O(VE)$.


Is the Syntax of C Language completely defined by CFGs? I think the Question is self sufficient. Is the syntax of C Language completely defined through Context Free Grammars or do we have Language Constructs which may require non-Context Free definitions in the course of parsing?

An example of non CFL construct i thought was the declaration of variables before their use. But in Compilers(Aho Ullman Sethi), it is stated that the C Language does not distinguish between identifiers on the basis of their names. All the identifiers are tokenized as 'id' by the Lexical Analyzer. If C is not completely defined by CFGs, please can anyone give an example of Non CFL construct in C?

The C language has typing rules. For example, you can't divide two pointers, and when you call a procedure accepting a pointer, you can't use a double. A C compiler analyzes its source in several phases: first there is lexical analysis, then the source is parsed, and so on. These phases are abstraction, and in fact additional information is passed from phase to phase. For example, even though the grammar of C doesn't care about names of variables, this information is passed, and that's how the attributed grammar can verify the typing rules. So there are additional mechanisms working on top of the grammar.

For an even simpler example, take the one given by Aho and Ullman. At the parsing phase, all variable names look "the same", yet you cannot use a variable unless it had been declared. This information is hidden from the context-free parser, but is retained as an attribute for the lexical phase, and is checked during parsing. The context-free grammar of C represents only some aspects of what legal C code is, which are useful for implementing a fast parser. On top of that parser, the other rules are checked, semantics are given to the C code, and machine code is generated.


Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$? The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary search ($T(n) = T(n/2) + O(1)$) and merge sort ($T(n) = 2T(n/2) + O(n)$).

  Do you know any algorithms (probably using "divide and conquer") that have the time complexity of the form $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + O(n)$?

Think of an algorithm, which do something linear with an integer list of length $n$, for example computes the maximum. Afterwards, the algorithm divides the list of length $n$ into $\sqrt{n}$ lists of length $\sqrt{n}$ and starts the algorithm for them. The result of the algorithm is for example the product of the computed maximum and the results of the $\sqrt{n}$ lists. For the base case, a list of length $1$, you can return  the value of the only element.

This algorithm has the time complexity, you asked for.


Is unification over regular expression equations doable? By way of example, suppose I know that $X + a = b + Y$ where $X$ and $Y$ are variables standing for regular expressions, then $(X, Y) = (b, a)$ is a solution to this set of equations.

Generalizing over all such equations, is there a computable (decidable) procedure for calculating the regular expressions which the variables must stand for in order for the equation to be solvable? Is there some kind of uniqueness, e.g. of minimal solutions?

In case the alphabet size matters: you can represent $\{1, \ldots, n\}$ in unary using just two symbols, so I assume the answer for $k$- and $m$-symbol alphabets are the same when $k \geq 2 \land m \geq 2$, in which case I care primarily for alphabets of size $\geq 2$—the reason I stress the word "assume" is that I know some properties of regular languages don't hold for regular expression equations (when suitably translated).

The application I have in mind is miniKanren-style logic programming.

Since families of sets closed under union form a semilattice, and the family of regular languages is one such closed family, programming with regular languages seems straightforward. For example, let each logic variable $V$ represent some indeterminate language $L$. For each $V$ store a pair of bounds $(sub, disj)$ expressing the knowledge $sub \subseteq L \land (L \cap disj) = \emptyset$, i.e. store two sets of strings for which the membership-ness is known. Grow them in the variable unification part and fail when $sub \cap disj \not= \emptyset$.

It would be nice to add logic over regular expressions and not just regular languages.  No obvious approach occurs to me, and I suspect it's a whole other ballgame.

I'm fairly sure this is possible. This seems to me as a special case of set constraints over tree languages: we can view regular expressions as a restriction of regular tree languages where each node has 0 or 1 children. These can handle union, concatenation, and recursion (star), and you can solve for variables like you describe.

They're decidable, even when we allow negation. You can see a great survey here:  https://theory.stanford.edu/~aiken/publications/papers/ppcp94.pdf In general, Alexander Aiken has a lot of great papers on set constraints.

You might find more of what you're looking for with "word constraints" or "set constraints over words". The complexity situation isn't great for trees, but it might be better for words.


Rotation matrix between two objects - alignment I am trying to align two objects based on the notion of points and their correspondence, but struggling to find a solution.

I have two objects A and B. However, they are rotated in a different direction, and therefore I would like them to align. I have a notion of some correspondence between the points in object A and in object B.

The initial idea that I had looks as follows. Pick two points( let's call them center and end point) in A, and then pick the corresponding points in B. Then measure the angle between them.

I believe that I could get an angle between them, but I am not sure how would that translate to the rotation matrix. I was also wondering whether it is not better to split it into different axes , and then perform multiplication. However, I am not sure how would I proceed with that.

Could anybody give me advice whether my approach is ok, or possibly provide a way of obtaining a rotation matrix for the whole object based on those vectors?

My idea:

Let's say that I have object A, and two points:

A0 = [2,4,6]

A1 = [3,5,7]

Then I calculate a vector

A0A1 = [1,1,1]

Then I find a corresponding two points in object B:

B0 = [4,8,12]

B1 = [2,7,5]

Then B0B1 = [-2,-1,-7]

Now I would calculate the angle

You probably want to find a homography that maps object A to object B.  I suggest reading about image rectification/alignment/registration.  A homography is a linear function of the form

$$q = Ap+b,$$

where $A$ is a matrix, $b$ is a translation vector, $p$ is a point from object $A$, and $q$ is the corresponding point from object $B$.

If you have four points from object A and the corresponding four points in B, you can solve uniquely for a homography that maps each of those A-points to the corresponding B-point (using linear algebra).  There are standard methods for finding that homography in the computer vision literature, based on solving a system of linear equations.  For instance, OpenCV has a method that will do that for you.

More generally, if your points have some small amount of error in them, it can be more effective to take more than four points and then find the best-fit homography.  For instance, you could take five points, or six points, or 10 points, and find the best-fit homography that maps those 10 points from object A (as close as possible) to the corresponding 10 points from object B.  This becomes a least-squares fit problem, where you want to minimize the sum of the squared distances between (homography applied to point from object A) and (location of corresponding point in object B).  There are ways to find that best-fit homography using a least-squares fit.

There's lots more one can say about the subject -- it has been studied extensively in the image processing and computer vision literature. See https://en.wikipedia.org/wiki/Point_set_registration for a starting point.


Decision problem - vertex with path to all other vertcies Consider the following decision problem: Given a directed graph $G$, is there a vertex $v$ that has path to all other vertcies.
I am able to place this problem in NL, similarly to the strongly-connected graph problem. But is this problem NL-complete? Thinking about reduction from $stCON$ problem, but can't get it through.

Suppose we are given a directed graph $G$ and two vertices $s,t$. Add a new vertex $a$ and an edge from $a$ to $s$. Also, add an edge from $t$ to all vertices in the graph apart from $a$.

Since $a$ has no incoming edges, if there is any vertex from which all other vertices are reachable, it must be $a$. For this to happen, in particular $t$ must be reachable from $a$. Since the only outgoing edge from $a$ points at $s$, this can only happen if $t$ is reachable from $s$. In that case, all other vertices are also reachable from $a$, via $t$, since we added outgoing edges from $t$ to all vertices apart from $a$.


What's the definition of ACTL? I have been looking for the definition of ACTL, but Google has given me very little to go with.

So far, I know ACTL is another form of CTL model checking, and CTL includes the following operators:

Always
Exist
Global
Finally
Next
AND / OR
NOT

So what does ACTL include and how is it different from CTL?

Many thanks

ACTL is the universal fragment of CTL.
Thus, existential path quantification is not allowed.
So a path formula is of the form $AF\psi$,  $AG\psi$, or $AX\psi$ (or a conjunction or disjunction of path formulas).

Moreover, you are not allowed a general NOT operator, but rather negations have to be on the atomic propositions (otherwise this fragment would be equal to CTL).


Efficient algorithm for conversion of hexadecimal fraction to decimal fraction Let's say I have some very long hex fraction like this:

0.3F30A21306AEFCBADE3230A593EFAEB395A39E

What are some algorithms with an acceptable complexity to convert it to the associated decimal string:

0.246835...

?

You can do better than quadratic in the length of the fraction, but doing so requires fast (subquadratic) multiplication algorithms such as Karatsuba or Schönhage-Strassen. First, multiply by a suitably large power of 10 to obtain an integer (note that the exponent of this power is at most linear in the length of the fraction). The problem is now to convert a hexadecimal integer to decimal.

Suppose multiplication of two $n$-bit integers takes $M(n)$ time ($O(n\log n\log \log n)$ with Schönhage-Strassen).

Conversion between (general) bases can be done using divide and conquer. Given a hexadecimal integer $k<10^n$, recursively compute decimal representations of $\left \lfloor{\frac{k}{10^{\left \lfloor{n/2}\right \rfloor}}}\right \rfloor$ and $k\textrm{ mod }10^{\left \lfloor{n/2}\right \rfloor}$. The decimal representation of $k$ can then be found by concatenating the two recursively computed representations.

Since division and mod can both be done in $O(M(n))$ time, on an $n$-bit integer this algorithm has running time $T(n)=2T(n/2)+O(M(n))$. For Schönhage-Strassen multiplication, this evaluates to $O(n\log n\log n\log \log n)$.


Pumping Lemma String Choice Let $A = \{ uu \text{ } | \text{ } u \in \{a,b\}^* \}$ be a language. Suppose that we want to prove that A is not regular via the pumping lemma, why is the string w = $a^{p} a^{p}$ not valid to derive a contradiction?

The pumping lemma states that if a language $L$ is regular, then there exists a pumping length $p\gt0$ such that for all strings $s$ in $L$ with length at least $p$, there exists a way to split $s$ in the form $xyz$ such that all of the following are true:

$xy^iz\in L$ for all $i\ge0,i\in\mathbb Z$
$|y|\gt0$
$|xy|\le p$

The contrapositive is:

For all pumping lengths $p\gt0$, if there exists a string $s$ in $L$ of length at least $p$ such that for all ways to split $s$ in the form $xyz$, at least one of the three statements (those mentioned above) are false, then the language $L$ is not regular.

When you prove that a language $L$ is not regular using the pumping lemma, you generally assume that it is regular, and prove that the premise of the contrapositive of the pumping lemma is true. This implies that the language is not regular, leading to a contradiction.

Now, in your problem, you would like to choose the string $a^pa^p$. As you can see in the contrapositive statement, the choice of choosing $x,y,z$ does not lie with you. So, you need to show that the contrapositive holds true for every choice of $x,y,z$, i.e., at least one of the three statements in the pumping lemma is false for every choice of $x,y,z$.

So, in general,
$$a^pa^p=a^{2p}=a^ia^ja^k$$
for some $i,j,k\ge0$ and $i+j+k=2p$. Note that $j\gt0$ for statement 2 to be true, and $i+j\le p$ from statement 3.

Now, all that needs to happen is $j$ to be even and $i=k$,which, in general, is possible as all possible ways of splitting the string need to be taken into account that suppose $j=2l$ for some $l\gt0$.
Then,
$$a^pa^p=a^ia^{2l}a^i=a^{i+l}a^{i+l}$$

Now, as per statement 1, suppose we pump $y$, we get $a^i(a^{2l})^na^i\in L$ for all $n\ge0,n\in \mathbb Z$. Note that for every choice of $n$,
$$a^{i+ln}a^{i+ln}\in L$$

So, for this string $s$, we have managed to find a way to split it, for any $p$, such that all the conditions of the pumping lemma hold. This does not show that the premise of the contrapositive is true, and hence does not lead to a contradiction. Thus, to show that it is not regular, you need to choose a more suitable string $s$ for all $p$ that results in the premise being true, which would imply that $L$ is not regular, leading to a contradiction.


Information about ε-greedy algorithms I'm working on a paper that uses ε-greedy algorithms for choosing episodes of a sarsa q-learning algorithms. I searched for algorithm but couldn't get so much. Can you please give me the algorithms and a little explanations about it?

ε-greedy is just a way to promote exploration in Reinforcement Learning. I would not classify SARSA or Q-Learning as ε-greedy algorithms.

The latter are very common reinforcement learning algorithms and you can definitely can find lots of material about them.

I would suggest to have a look at this classic book (the draft for the second edition is available for free)

https://webdocs.cs.ualberta.ca/~sutton/book/the-book.html

Another shorter and excellent resource is (have a look at chapter 21):

Russell SJ, Norvig P, Davis E. Artificial intelligence: a modern approach. Upper Saddle River, NJ: Prentice Hall; 2010.

EDIT:

The paper you posted is using SARSA(λ), it is not the same as SARSA. You will need to go through a few Sutton chapters for that to make sense. You won't find it in Russell.

The link to SARSA(λ) in Sutton (1998) HTML version is here: webdocs.cs.ualberta.ca/~sutton/book/ebook/node77.html

However, I think you will need to read at least chapter 6 before jumping into eligibility traces


Term for open-ended algorithms There are some enumeration problems which have little input, except for some termination criterion. Examples for the question at hand would be

enumeration of prime numbers in ascending order
enumeration of grid points by increasing distance

For these there exist two fundamentally different techniques:

With one class of approaches you have to state the scope of your question up front. You'd state the upper bound for the primes you want, the maximal distance, or similar. The Sieve of Eratosthenes would fall into this category, as would an algorithm enumerating all points in a rectangle and then sorting them by distance.
With another class of approaches, you don't have to state the extent of the required output up front. You can see the enumeration as a lazily evaluated infinite sequence, and feed it to some other part of your code that should eventually terminate the generation once a generated output satisfies your requirements. Testing each odd number against a list of already found primes would be an example from this class.

Now I'm looking for a term to distinguish these two forms. Somehow the latter approach feels closely related to online algorithms, which is why I added that tag. But every deifnition I could find specifies an online algorithm as processing its input incrementally. There is almost no input here, unless you count the one-bit decision between “give me the next item” and “that's it, stop now” as an incremental input. Would calling this an online algorithm be appropriate, or is there a better term?

Informally, you might call this lazy evaluation, or a lazily-evaluated stream.

A $O(f(n))$-time delay algorithm is guaranteed to output a stream of answers, with a delay of at most $O(f(n))$ time between answers.  One consequence is that outputting $k$ answers will take at most $O(k \times f(n))$ time -- but you also know that you won't ever have to wait too long for the next output.  (So, this helps rule out algorithms that return the first $n$ answers very rapidly and then take a really long time to return the $n+1$th answer).

An output-sensitive algorithm is an algorithm that outputs a stream of answers, and where the running time is some function of the length of the output.  Normally we evaluate the running time of an algorithm as a function of the length of the input, but an output-sensitive algorithm is analyzed in terms of the length of the output.  That's potentially relevant here.  Suppose your goal is to enumerate all fidgets in a warbuggle.  If you find an polynomial output-sensitive algorithm for this task, then you have an algorithm that's potentially useful for streaming purposes -- in particular, the average delay between outputs isn't too large (though the worst-case delay could potentially be quite high).

If neither of them captures exactly the concept you have in mind, then I suggest you just describe in text what properties your algorithm has, and don't worry too much about finding a short term for it.


Countably many oracle Turing machines? In Sipser's text, when proving that there exists an oracle $A$ such that $P^A \ne NP^A$, he writes:

  Let $M_1, M_2, \ldots$ be a list of all polynomial time oracle TMs.

I understand that there are countably many Turing machines, but aren't there uncountably many oracles?

There are $2^{\aleph_0}$ possible oracles, but when fixing an oracle $A\subseteq \Sigma^*$, there are only countably many Turing machines $M^A$ with access to the oracle $A$.

Remember that a Turing machine with access to some oracle is defined in the same manner as a normal Turing machine, but with an additional operation (they can query the oracle). They have a special tape on which they can write a query, and say, three additional special states $q_{ask},q_{yes},q_{no}$. Upon entering $q_{ask}$, if $s\in\Sigma^*$ is the content of the query tape, the machine enters either $q_{yes}/q_{no}$, depending on whether or not $s\in A$.

Nothing stops us from encoding such machines as strings, in the same way we encode regular Turing machines, hence we only have countably many such machines.


Factorial usage within proof using the pumping lemma We are going over the pumping lemma in class and we recently went over the following example:

Let
$$ L = \{ w \mid w \text{ has a different number of 0s and 1s} \} $$
Consider
$$
s = 0^P1^\left(P+P!\right)
$$
$ s $ can be divided into $ s = xyz $
Consider
$$
y = 0^m; 0 \leq m \leq P
$$
Let
$
i = \frac{P!}{m} + 1
$

$$
xyz = 0^\left(P + \left(i - 1\right)m\right)1^\left(P + P!\right) \notin L
$$

Forgive me if the example is not put together well. This example didn't quite get finished in class. Feel free to expand on this if need be.

However, my question is how does one know to use a factorial in the first place when approaching this proof?

Let's choose a different word in step 2, say $s' = 0^a1^b$, where $a$ and $b$ depend on $P$ and $a \geq P$ (to force an $y$ that has the form $y=0^m$).

It's important to show that for any length $m, 1\leq m \leq P$ there is no valid division $s' = xyz, y = 0^m$ (valid means it fulfils the conditions of the pumping lemma).

So for every such $m$, we need an $i$ such that:
$xy^iz = x0^{im}z = 0^{a-m+im}1^b  = 0^{a+(i-1)m}1^b {! \atop =}  0^b1^b$.
This means that $m$ must divide $b-a$ for every $m$. One number $b-a$ that fulfils this, is $P!$, so e.g. $a=P$, $b=P+P!$, the least common multiple of $1,\dots,m$ is another possible choice for $b-a$.


Logspace algorithm for balanced parentheses problem Currently I want to learn the complexity of space, I read a few of the books on it. On this I encountered this example problem. I would just like to know how to show that the following problem $\in L $ (deterministic logarithmic space).

Input:  series of open or closed parentheses

Question: Are these parentheses properly balanced?

Example:  $((() ()) (()))$ should be accepted but $()) ()$ should be rejected.

Initialize a counter at zero. Whenever you see "(", increase it by one, and whenever you see ")", decrease it by one. Accept if the counter was always nonnegative and ended up at zero. The counter only takes logarithmic space to store.


How to connect the math of recurrence relations to daily programming concepts What exactly are we doing from a CS perspective when we solve a recurrence relation and find a resulting formula for a sequence given a set of initial conditions? I just went through the "linear homogeneous recurrence relations of degree k with constant coefficients" bit in discrete math and basically understand the math part and have a simple process for solving them mechanically.

What I haven't seen yet is an explanation of what this correlates to in a CS sense. I understand we will encounter recurrence relations in algorithms which we haven't reached yet (next class) but I'm wondering what exactly do the initial conditions and the sequence represent?

For a trivial programming example, if we were to write a recursive function to process a directory and all its subdirectories, I understand conceptually that could be modeled as a recurrence relation because it is recursive, but I don't know how, and I don't know what the initial conditions and final formula for the sequence would represent in such a scenario.

Here's an example of the type of relation I'm talking about. So we solve these by taking the relation down into its characteristic equation, finding the roots, and then building a system of equations from the initial conditions $a_0, ..., a_j$ that we solve to find the constants. Finding the constants gives a closed formula for that particular sequence defined by those initial conditions.

My question is, from a CS/programming/software engineering perspective what would we model using recurrence relations like this other than algorithms, and what would the initial conditions represent in those models?

In computer science, recurrence relations are often useful for analyzing the running time of algorithms.  For instance, we might define a function $T(\cdot)$, so that $T(n)$ is the running time when running the algorithm on an input of size $n$.  Often, for many kinds of algorithms, we can write a recurrence relation that expresses $T(n)$ in terms of smaller values, such as

$$T(n) = 2T(n/2) + O(n).$$

This would be saying that the running time to solve a problem of size $n$, is twice the time to solve a problem of half that size (perhaps because we recursively solve the first half and the second half using the same algorithm), plus $O(n)$ more (perhaps to combine/merge their two solutions).

So, the numbers represent running times -- the number of operations the algorithm takes to solve the problem.  You might like to take a look at Reference answers to frequently asked questions and How to come up with the runtime of algorithms?.  Also take a look at algorithms textbooks, especially their chapters on running time analysis and divide-and-conquer algorithms.

The initial condition of a recurrence (e.g., the value of $T(1)$) depicts the running time of the algorithm on a small instance.  Often, for a recursive algorithm, this is the running time of the base case.

In computer science, the sequence we are considering is

$$T(1),T(2),T(3),T(4),T(5),\dots,$$

i.e., the sequence of running times as the input size increases.  If you were to write down the sequence of running times for some algorithm, you might spot a pattern, where each term can be computed by a simple formula of a few previous terms (namely, the pattern indicated by the recurrence relation).  That said, honestly, thinking about this as a sequence might not be the most helpful or intuitive viewpoint (at least, I don't find it to be so); I find it more intuitive to think of $T(\cdot)$ as a function rather than a sequence.  The same mathematics still applies.

Another way to get some intuition is to work through a few examples where recurrences are used to analyze the running time of some simple algorithms.  I think that will also help you get a better intuition of what the mathematical expressions mean and how they relate to the algorithm.


Average Case Analysis for finding max and min value on an array Given the following algorithm, to find the maximum and minimum values of an array - don't mind the language:

MaxMin(A[1..n])
    max = A[1];
    min = A[1];
    for (i = 2; i<=n; i++)
        if (A[i] > max)
            max = A[i];
        else if (A[i] < min)
            min = A[i];
    print(max, min);

I need to do a probabilistic analysis for the average case of comparisons that will be made on its execution.

So far, my solution is:

Given an indicator random variable:
$$
X_i =
 \begin{cases}
   \text{1, if max $>$ $A[i]$}\\
   \text{0, if max $<$ $A[i]$}\\
 \end{cases}
$$

and assuming an uniform distribution for $A[1..n]$, the expected probability is:
$$E[x] = \sum\limits_{i=1}^{n} Pr(X_i)$$

where $$Pr(X_i)$$ is the probability of the i-th element be the $max$ element in $A[1..n]$. It's possible to determine that:
$$Pr(x_1) = 1, Pr(x_2) = 1/2, Pr(x_3) = 1/3 ,..., Pr(x_n) = 1/n$$
and thus for an array of size $n$ the expected value can be calculated as:

$$E[x] = 1 + 1/2 + 1/3 + ... + 1/n = \sum\limits_{i=1}^{n}{\frac{1}{i}} \approx \log{n}$$

And the same goes for $min$, which will give the same result $\log{n}$. (1)

My questions are: is it correct? Does the complexity for the average case of the given algorithm is $\theta(\log{n})$? Can I use the argument pointed by (1), just modifying $X_i$ so:
$$
X_i =
 \begin{cases}
   \text{1, if min $<$ $A[i]$}\\
   \text{0, if min $>$ $A[i]$}\\
 \end{cases}
$$

I already read this (unfortunately the link to the video isn't available), but it only explains for $max$ and my analysis must be for both $max$ and $min$.

First, note that the first comparison will always compare $n-1$ times, independent of the distribution of the input. So, what you really want to know is how many times the second part of the if compares. For this, you can use a indicator random variable like this:

$$
X_i =
     \begin{cases}
       \text{1, if A[i] $\le$ $\max$}\\
       \text{0, if A[i] $>$ $\max$}\\
     \end{cases}
$$

So, just like you did, assuming an uniform distribution for $A[1..n]$, the expected probability is:

$$E[x] = \sum\limits_{i=1}^{n} Pr(X_i)$$

But we do not want $Pr(i=\max)$, we want $\overline{Pr(i=\max)}$, like we stated before. So, using your probability of the $i-th$ element to be the $max$ element:

$$Pr(i = \max) = 1/i$$

We have this complement:

$$\overline{Pr(i=\max)} = (1 - 1/i)$$

From which we can put in the expected probability:

$$E[x] = \sum\limits_{i=2}^{n} (1 - 1/i) = \sum\limits_{i=2}^{n}1 - \sum\limits_{i=2}^{n}1/i = n - 1 - (\ln|n| - 1 + \Theta(1))$$

So, to get the total quantity of comparisons, we can just sum the number of comparisons of the two parts. Note that the $\Theta(1)$ can absorb a constant values.

$$(n - 1) + n - 1 - \ln|n| + 1 + \Theta(1) = 2n - 1 - \ln|n| + \Theta(1)$$

And we get the expected total number of comparions:

$$2n - \ln|n| + \Theta(1)$$