Closest divisors in array Given an array $A[1],\ldots,A[n]$ of natural numbers, we have to construct a new array $B[1],\ldots,B[n]$, where $B[i]$ is equal to $A[j]$ for the minimal $j > i$ such that $A[j]$ divides $A[i]$, or $-1$ if no such element exists. For example:
$$
\begin{array}{c|ccccccc}
A & 10 & 4 & 5 & 2 & 1 & 8 & 4 \\\hline
B & 5 & 2 & 1 & 1 & -1 & 4 & -1
\end{array}
$$

I can solve this in $O(n^2)$ using brute force. Is there a better solution?

No, probably not, if you care about theoretical worst-case running time.  The problem is as hard as the subset containment problem: given sets $S_1,\dots,S_n$, check whether there exists sets $S_i,S_j$ such that $S_i \subset S_j$.  It's known that there is no algorithm with $O(n^{2-\epsilon})$ running time, assuming the SETH conjecture is true.  Thus, any faster algorithm would imply a disproof of SETH, which is a famous open problem -- so you shouldn't expect any easy algorithm that does significantly better than $O(n^2)$ in worst-case running time.  (I don't count a $\log n$ factor speedup as significant.)  See https://cstheory.stackexchange.com/q/9896/5038.

If you only care about the "average case" it might be possible to do better.  The answer might also depend on the model of computation and the size of the integers, so it's possible there might be some choice of those that lets you evade this hardness result.

For instance, if your numbers are "random" in a particular specific way, you can use a divide-and-conquer algorithm.  First recursively solve the problem for $A[1..n/2]$, and recursively solve the problem for $A[n/2+1..n]$.  Then for each $i \le n/2$ such that $B[i]=-1$, we'll find the smallest $j > n/2$ such that $A[j]$ divides $A[i]$ and overwrite $B[i]$ with $j$.  Suppose we can do that last step in $U(n)$ time.  Then the total running time will satisfy the recurrence $T(n) = 2 T(n/2) + U(n)$, i.e., $T(n) = O(U(n) \log n)$.

OK.  So how will we do that last step?   We'll solve that problem in turn using a separate divide-and-conquer algorithm.  Pick a prime number $p$ that hasn't been picked yet, and construct the sets $S^0 = \{i : p \not| A[i], i \le n/2\}$, $S^1 = \{i : p | A[i], i \le n/2\}$, $T^0 = \{i : p \not| A[i], i > n/2\}$, $T^1 = \{i : p | A[i], i > n/2\}$.  Now for each $i \in S^0$, find the smallest $j \in T^0$ such that $A[j]$ divides $A[i]$; and for each $i \in S^1$, find the smallest $j \in T^0$ such that $A[j]$ divides $A[i]$ (or, equivalently, such that $A[j]$ divides $A[i]/p$), and find the smallest $j \in T^1$ such that $A[j]$ divides $A[i]$ (or, equivalently, such that $A[j]/p$ divides $A[i]/p$).  Those are three subproblems each of size $n/2$ (heuristically, assuming the numbers are random and half are divisible by $p$ and half aren't), and then you can combine them to get a solution to the original problem in $O(n)$ time, so the total running time to do this last step is $U(n) = 3 U(n/2) + O(n)$, which solves to $U(n) = O(n^{\lg 3}) = O(n^{1.585})$.

So, heuristically the total running time of this approach is $O(n^{1.585} \log n)$ under a particular assumption on the distribution of the numbers.


Grammar of regular languages vs. context free languages Let $L$ be some language.
What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language?

For example, in case $L$ is regular,
could you say that there exists a context-free grammar $S$ such that every derivation rule of $S$ is of the form:

$$V \rightarrow \sigma_1 \sigma_2 \cdots \sigma_k V_1V_2 \cdots V_m$$

In other words, the prefix of the rule contains only symbols of $\Sigma$ and the postfix contains only variables of $V$.

If the language is regular, then it can be defined using rules of the form $A \to \sigma B$ and $A\to \varepsilon$ by just simulating a finite state automaton. Here the nonterminals $A,B$ represent states of the automaton, and a production of the first type corresponds to a transition from $p$ to $q$ with label $\sigma$. The latter type of productions is for a final state $A$.  Thus, when we use this construction the number of variables equals the number of states. As we know this number cannot be bounded.

Grammars of this type are called right-linear. Nowadays they are sometimes called regular grammars (but I am not fond of this as I would prefer regular to distinguish the expressions of that name).

If you do not like $\varepsilon$-production then we can take productions $A\to \sigma$ for transitions leading into a final state. But in this way we cannot produce the empty string.

Every context-free language can be generated by rules of the form $A \to \sigma B_1\cdots B_m$.  This is called Greibach normal form. In general we can restrict to $m\le 2$ for this normal form. Restricting to $m\le 1$ will (of course) give only regular languages.

Greibach normal form is special as in each derivation step a letter is produced.


Meaning of $|w| ≡ 2 \mod 3$ I'm new to formal language and automata theory and I was left alone with this exercise. The task is to define a formal grammar for given language.

$Σ \in \{a,b\}$

$L = \{ w \in Σ^*\, |\, |w| \equiv 2 \mod 3 \} $

I already solved tasks of that kind, but now i struggle to understand what $|w| \equiv 2 \mod 3$ means. $|w|$ means the length of $w$ right? Does $\equiv 2 \mod 3$ mean that $|w|$ should be $2$ (because 2 modulo 3 is 2)?

Yes, $|w|$ is the length of $w$.

So $|w| \equiv 2 \mod 3$ means that the length of w divided by three should have the remainder 2. It should be from the set $\{2, 5, 8, \dots\}$.


Search String Algorithm in Table For a given database table:

DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y0
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

There exists an input with expected output based on a string search/match on the table. What we are trying to do is match the input with a combination of rows from the database. The only portion of the row that we use for matching is from w1 to w4. We then use the v column to identify the row. So, for example, the input string E would produce output X5, while input A, B would produce output Y0. In the case that there is no exact match, we want the elements closer to the front of the list to represent as long a string as possible. For example, with input A, B, C, D, E we could match a number of ways, notably Y1, X4, X5, X1, Y2, X5. We prefer the former, because A, B, C (from Y1) is longer than A (from X1). We want the first item in the output to represent as long a string as possible, and only when two potential outputs have the same length for the initial item do we try to get the longest second item we can.

Example 2:

input = A, B, C, D, F

expected_output => Y0, Y3

Explanation:

We would like to find A, B, C, D, F, but there is no match.

Likewise, we would match A, B, C, D if we could, but we cannot.

We do find Y1 is a match for A, B, C, so we use that. Our partial solution is Y1.

Now we look for D, F, but we don't find it.

We find X4 matches D, so our partial solution is Y1, X4.

Next we look for F but then there is no match. At this point we backtrack until we find a solution that does work. We take X4 off our solution and look for a better match for D, but there is no other way to match it, and we can't match a shorter substring, because that would be empty.

We take Y1 off our solution (now it is empty) and look for another way to match A, B, C. There is no other way, so we look for A, B, which we find with Y0. Our partial solution is Y0.

Now we search for the remainder of the input, C, D, F and we find it with Y3. Our solution is Y0, Y3.

Question:

What algorithms could I use or learn to be able to solve this efficiently?

What is the pseudocode or high level overview of how to solve the problem?

I wrote some code in Python to solve this problem. Python is designed to be very readable. There is a plaintext explanation of the algorithm below to help you understand what's going on. I am treating the database as an array indexable by its columns and rows.

def find_match(db, input_string):
    if input_string == '':
        return list()
    matches = list()
    length = 0
    for row in db:
        for col in [w1, w2, w3, w4]:
            if len(input_string) == length:
                return list(row[v]) # we found a match!
            if row[col] != input_string[length]:
                length = 0
                break
            length += 1
        if length == 0:
            continue
        if len(input_string) == length:
            return list(row[v]) # we found a match!
        matches.append((length, row[v]))
    matches.sort(reverse=True) # this puts longest matches first
    for length, match in matches:
        solution = find_match(db, input_string[length:])
# input_string[length:] means the input_string from index length till the end.
        if solution != []:
            return list(match) + solution
    return list()

Explanation:

This is a recursive algorithm to match the input. What it does is it loops over all rows in the database and finds all the ones that could be part of a match. If it finds anything that is a complete match, then it returns it immediately (there's no point going any further once you've found a solution.)

Then it sorts this list of potential matches so that the longest ones are evaluated first. It loops through these sorted matches and calls the find_match function using the portion of the input string that still needs to be matched, if that match is the one to be used. In this way, you are evaluating the longest matches first, as you requested.

A step-by-step example (Example 2 from your question):

DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y0
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

input_string: [A, B, C, D, F]

input_string is not empty, so we construct matches as an empty list. This is the list of rows that could be part of the final solution (they must entirely match the input string from the beginning until they run out of characters)

We loop over the rows, and find the following potential matches:
X1 (A); Y0 (A, B); Y1 (A, B, C)

We add them to the list as a tuple containing their length and the v that corresponds to them. This way we will be able to make sure we check the longest matches first. matches looks like this once we finish iterating over the db:
[(1, X1), (2, Y0), (3, Y1)]

Next we sort the list using the length as the key so the longest matches are first:
[(3, Y1), (2, Y0), (1, X1)]

Now we iterate over the matches, and try to find a solution using each one. Because we are calling the function recursively, it could be a long time between checking each match, depending on the length of the input string that still needs to be matched.

The first row we try to find a solution with is the first element in matches: Y1 (A, B, C). We call find_match(db, [D, F]) using [D, F] as the input string because that is the portion that still needs to be matched if we use Y1 (A, B, C). We can easily find the input string because we have the length (3, in this case) and so we take input_string from its 3rd index on:

A, B, C, D, F
0, 1, 2, 3, 4
X  X  X  D, F

input_string: [D, F]

we loop over the rows and find only one match: X4 (D)

Our list of matches is [(1, X4)], so we call find_match(db, [F])

input_string: [F]

we loop over the rows and find 0 matches, so matches is [] and when we iterate over it, we immediately continue on to the next block of code which tells us to return []. This is our way of saying we didn't find any match.

Now we go back to when input_string was [D, F]. We set solution equal to [], because that's what we just returned. Our only potential match was (X4, D), which we just checked, so now we are done iterating over the potential matches. Because we couldn't find any match with [D, F] as the input string we return [] as well.

Now we go back to when [A, B, C, D, F] was the input string and we had just finished trying to match Y1. We continue iterating over matches ([(3, Y1), (2, Y0), (1, X1)]). We call find_match(db, [C, D, F]) using Y0 (A, B) as the match.

input_string: [C, D, F]

We loop over the rows and we would get X3 (C); Y3 (C, D, F); Y4 (C, D, G) as our matches, but once we find that Y3 (C, D, F) exactly matches the input string, we go ahead and return [Y3]

Now we go back to when [A, B, C, D, F] was the input string and we were just using Y1 (A, B, C) as the match. At this point we see that we did find a match (the function returned [Y3]) and we add Y1 to it so that we have the full match: [Y1, Y3]. We return that and the function is done executing.

In the part of the function that compares the row with the input string, there is a little bit of bounds checking to make sure we only take as many characters from the row as it has, and we don't try to match the input string with a row that is longer than it is, but I didn't bother elaborating on that because it never came up in this example.


In general, how does a DFA know how to successfully process a string the intended way? Suppose we have:
$$A\text{ }\colon=\{x, y, z\}$$
$$M\text{ }\colon=\text{some DFA using A}$$
$$S\text{ }\colon=xyzxyzxyz$$
Intuitively, one might say $S$ is fed to $M$ on a per-character basis.
This means that somehow we have an undisclosed mechanism that can tell where a symbol starts and ends.
One might say, simply use the maximum valid substring similar to how Lexers tokenise plaintext. To that I say, suppose instead that we defined $A$ as:
$$A\text{}\colon= \{x, xx, xxx\}$$
Now we have 3 unique symbols, that, as it so happens, using the maximum valid substring will yield in a restriction to what our our $M$ can actually process, because any string longer than 2 characters will always be assumed to start with $xxx$ rather than perhaps, $x$ and $xx$.
One way I see around this is to actually have a character synonymous to a symbol. That is, $x$ and $xxx$ (from $A$) are both a single character each.
Thoughts?
EDIT
In the case my question is unclear:
The extended transition function is defined so as to extend the processable input of a DFA from simply one alphabetic character at a time, to an arbitrary amount. Usually we go about defining it as follows for a string wa:
$$\hat{δ}(q,w) = δ(\hat{δ}(q, x), a)$$
My issue is: What is converting the input from a string to a partition? Whatever this object may be, it has to follow some lexing rules, does it not?
Are there any conventions that go about this?

The transition function of a DFA has the type $\delta : (Q \times \Sigma) \rightarrow Q$. That is, it's a function that takes a state (from the set of states) and a symbol (from the set of symbols) and returns another state.
This function doesn't have to know anything about tokenization. It's given a single symbol, and that's all it cares about.
Similarly, the input to a DFA is generally defined to be an ordered series of symbols: this is what "a string over the alphabet $\Sigma$" means mathematically. If it helps, think of it as a "list" rather than a "string" in programming terms. So if the alphabet were $\{x, xx, xxx\}$, then the input might look something like $[x, xx, xxx, x, xx, xxx, x, xx, xxx]$. No ambiguity there.
In practice, most real-world DFA implementations (like foma) do have to care about tokenizing. But the details of how to do that are up to the implementation; the definition of a DFA doesn't care one way or the other.


Regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$ Design a regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$

So basically we have the language $L=\{11,011,110,0011,1100\ldots\}$.
I find the expression to be $R=(0+1)^*11(0+1)^*$.
But I found here the answer to be $R=(0 + 10)^*(11 + \epsilon)(0 + 10)^*$.
I cannot differentiate these two answers and the logic behind the later answer.
EDIT: In my answer, the first $(0+1)^*$ may provide $11$, so after this another $11$ is not permissible since at most one pair of $11$ is required. But what's the logic behind $(11+\epsilon)$?

The logic behind $(11+\epsilon)$ is to either allow a $11$, or allow no such pairs. The question states "[...] containing at most one pair [...]", and therefore we need to allow either one or zero pairs, and this is achieved by $(11+\epsilon)$.


Given a CFG G (in Chomsky normal form) and a string w, determine whether w has more than one parse tree in G in polynomial time So I have the following language:
C = {<G,w>|G is a CFG in Chomsky normal form and w has more than one parse tree in G}
How to prove that this language is in P (decidable in deterministic polynomial time)?
I tried to come up with a polynomial-time algorithm and tried to show a reduction to a different language in P, but couldn't figure it out.

You can modify the CYK parsing algorithm so that it counts the number of parse trees for each word.
Given a word $w = w_1 \ldots w_n$, for each $1 \leq i \leq j \leq n$ and non-terminal $A$, we will count the number of parse trees rooted at $A$ and generating $w_i \ldots w_j$. If $i = j$ then this number is either zero or one, depending on whether $A \to w_i$ is a rule. Otherwise, all parse trees are of the form $$A \to BC \to^* (w_i \ldots w_k) (w_{k+1} \ldots w_j)$$
and so if we know, for each $i \leq k < j$ and for each $B,C$ such that a rule $A \to BC$ exists, how many parse trees there are for $w_i \ldots w_k$ rooted at $B$ and for $w_{k+1} \ldots w_j$ rooted at $C$, then we can count the number of parse trees of $w_i \ldots w_j$ rooted at $A$.
You are interested in whether the number of parse trees of $w_1 \ldots w_n$ rooted at $S$ is larger than one or not. Therefore you can cap the numbers at two, thus avoiding large numbers and so reducing the running time.


Lookahead set: Determining minimum $k$ such that $G$ is a strong $LL(k)$ grammar How do we determine minimum $k$ such that $G$ is a strong $LL(k)$ Grammar

Like for grammar $G$ with the following rules
$S\rightarrow aAcaa \mid bAbcc,A\rightarrow a \mid ab \mid \epsilon$

I do not believe one can obtain directly a minimum $k$ such that $G$ is a strong $LL(k)$ grammar. However, as it is possible to (dis)prove that a grammar is strong $LL(k)$, one can iterate the proof over $k$.

A grammar $G$ is strong $LL(k)$ iff for every pair of distinct production rules $A \to \alpha$ and $A \to \beta$ (with $\alpha \neq \beta$), we have:

$$
First_k( \alpha \; Follow_k(A) ) \; \cap \; First_k( \beta \; Follow_k(A) ) = \emptyset
$$

The steps to obtain a $k$ for a certain grammar $G$ are thus as follows:

For each $n > 0$:

Check wether $G$ is $LL(n)$
If so, try proving $G$ is $LL(n)$
If not, we have found our $k = n - 1$

Some documents that might help with the actual proof:

About first and follow sets (LL(1))
Obtaining first and follow sets (LL(k)) with example


Assigning a unique representation to equivalent circular queues First, a few vague definitions:

Circular queues (or circular buffers) are data structures like normal queues but with their ends connected together (forming a "circle").
wikipedia

Let's say that 2 circular queues are equal if they have the exact same elements in them and the order of items in them are exactly the same.

Example: if we form  a circular queue from the string "absa" and one from "bsaa", the two will be equivalent.

My task is to group together "cyclic equivalent" strings. I'm trying to find a "base representation" for all "cyclic equivalent" strings to use it as an "index" in a hash table which would make grouping them more efficient.

Help me find an algorithm that can assign a single unique representation to all equal circular queues!

is it even possible? (let alone useful?)
what about problematic ones like "asdasd"? (see balanced bike wheel analogy)

Some ideas to base the algorithm on:

bicycle wheel analogy: Imagine your bike's wheels have colored spokes, all kinds of colors, each color having a different weight (terrible idea for everyone except for computer scientists). If you flip your bike upside down letting the wheel spin freely, the part of the wheel with the most torque will rotate to the bottom and the wheel will stay in that "base position" and that bottom point of the wheel could be called its "base index". If we recorded the order of the colored spokes starting at that point, that order could be called a linear "base representation" of the wheel. This would not happen in the case of a properly balanced wheel, which would not start rotating. What could we do in that case?
?

Some practical use cases:

finding equivalent circular transportation routes on a map (like those of public transportation) regardless of starting and ending point
?

Enumerate all possible rotations of the queue.  Take the lexicographically first of them.  Use this as your representative.  If you want a short index into a hash table, take the hash of that.  Then any two equivalent queues will get the same representative / same index.

If the queue has $n$ items, implementing this naively takes $O(n^2)$ time.  However, it can be done more efficiently.  When the contents of the queue are random, sorting the rotations lexicographically, using a string comparison operator that only compares as much of a prefix as necessary to find the first mismatch, will have running time $O(n \log^2 n)$.  If you want to get more fancy, you can do it in $O(n)$ time, using a suffix tree or suffix array; though the constant factors and implementation complexity probably won't make this worthwhile unless your queues are extremely large.


Path in a graph with a given xor of weights of edges I have an undirected weighted graph with $V$ vertices and $E$ edges. Weight of a path is a xor of weights of the edges on this path. Paths can pass through the same vertices and edges many times. Given two vertices $a$, $b$ and some number $x$ I want to tell if there exists a path of weight $x$. What is the fastest algorithm to solve this problem?

Arbitrary paths

If you want to know whether there exists a not-necessarily-simple path from $a$ to $b$ with weight $x$, here is a one-sided test:

Compute a cycle basis for the graph, $c_1,\dots,c_k$; this can be done in polynomial time.  Let $p$ denote any simple path from $a$ to $b$.  Let $W(p)$ denote its weight and $W(c_i)$ the weight of the cycle $c_i$.  Then there exists a path of weight $x$ only if $x \oplus w$ is in the linear span of $W(c_1),\dots,W(c_k)$ (with all operations taken over $\mathbb{F}_2$).  This condition can be tested in polynomial time.

Why does this work?  If there exists a path from $a$ to $b$, then it can be written as the xor (symmetric difference) of $p$ and some subset of $c_1,\dots,c_k$.  Thus, its weight is given by $W(p)$ xored with the selected $W(c_i)$ values.

However, the converse doesn't necessarily hold.  If $x \oplus w$ is in the linear span of $W(c_1),\dots,W(c_k)$, there is no guarantee that there exists a path from $a$ to $b$.  (The linear combination of $W(c_1),\dots,W(c_k)$ might correspond to a set of cycles that form a disconnected graph, and doesn't provide any way to form a path from $a$ to $b$.)

I don't know whether there is a polynomial-time algorithm or not.

Simple paths

If you want to require the path to be a simple path, then the problem is NP-complete, by reduction from Hamiltonian path.

Let $G$ denote your graph.  Suppose it has $n$ vertices, with vertices numbered from $1$ to $n$.  Modify it to replace each vertex $v$ with two copies $v_0$ and $v_1$, and add an edge between $v_0$ and $v_1$.  For each edge $(u,v)$ in the original graph $G$, we'll introduce edges $(u_1,v_0)$ and $(v_1,u_0)$ in the new graph, with weight zero ($0^n$).  Each the edge $(v_0,v_1)$ will have a weight from $\mathbb{F}_2^n$ that has the $v$th bit set and all other bits clear (i.e., its weight is $0^{v-1} 1 0^{n-v}$).  Let $x$ denote a weight with all bits set (i.e., $1^n$).

Now there exists a simple path from $a_0$ to $b_1$ of weight $x$ in the new graph if and only if there exists a Hamiltonian path from $a$ to $b$ in the original graph.  Therefore, any algorithm for your problem with paths restricted to simple paths immediately yields an algorithm for the Hamiltonian path problem, which is known to be NP-complete.


Tutorials/resources for building a toy SMT solver I've built a rudimentary SAT Solver from scratch, and wanted to do the same with SMT solvers as well.
While I've found two toy SMT Solver implementations in Haskell and Ocaml, but no tutorials or examples, which is a stark contrast from all SAT Solver tutorials out there.
Is there a resource for building a toy SMT Solver from scratch?

I think these slides give a foundation of building a SMT solver, somewhat


Can someone explain why there are two summations here? The following quote is from the book "The art of computer programming":

  (..) sentence  would presumably be used only if either $j$ or $k$ (not both) has exterior significance.

  In most cases we will use notation (2) only when the sum is finite - that is, when only a finite number of values $j$ satisfy $R(j)$ and have $a_j \neq 0$. If an infinite sum is required, for example
  $$\sum_{j=1}^{\infty} = \sum_{j \geq 1}a_j = a_1 + a_2 + a_3+\cdots$$
  with infinitely many nonzero terms, the techniques of calculus must be employed; the precise meaning of (2) is then
  $$\qquad\qquad \sum_{R(j)} a_j = \left(\lim_{n\rightarrow\infty} \sum_{R(j) \atop 0\leq j \leq n} a_j\right) + \left(\lim_{n\rightarrow\infty} \sum_{R(j) \atop 0\leq j \leq n} a_j\right),\qquad\qquad(3)$$

  (...)

And why are they exactly the same? I showed a math professor and he thinks they're labelled wrong but couldn't figure it out. I don't even get why there are two.

Sorry if the question isn't clear enough. I'm referring to the two infinite sums. As far as (2) is concerned he is only referring to what is on the left hand side of the equation with the two infinite sums. Its just a way of representing any possible series. So essentially my question is how does making any series go to infinity make two of them? Or am I misunderstanding?

Also I tried to post this in math stack exchange and it wouldn't let me so I came here since its from the book, the art of computer programming.

And why are they exactly the same? I showed a math professor and he
  thinks they're labelled wrong but couldn't figure it out. I don't even
  get why there are two.

When in doubt, check the book's errata (Page 4).

  $$ \sum_{R(j)} a_j = \Bigg( \lim_{n\rightarrow \infty} \sum_{\color{red}{{\substack{R(j)\\-n\leq j<0}}}} a_j \Bigg ) + \Bigg(\lim_{n\rightarrow \infty} \sum_{{\substack{R(j)\\0\leq j< n}}} a_j \Bigg) $$

Because $R(j)$ is a relation involving $j$, so you must check whether it's satisfied for negative values as well.

The previous paragraph also has a typo:

  $$ \color{red}{\sum_{j=1}^{\infty} a_j} = \sum_{j\geq 1} a_j = a_1 + a_2 + a_3 + \cdots $$


How can I improve my Algorithm? This is a problem from Interview Street in Dynamic Programming section.
  https://www.interviewstreet.com/challenges/dashboard/#problem/4f2c2e3780aeb

  Billboards(20 points)

  ADZEN is a very popular advertising firm in your city. In every road you can see their advertising billboards. Recently they are facing a serious challenge , MG Road the most used and beautiful road in your city has been almost filled by the billboards and this is having a negative effect on the natural view.

  On people's demand ADZEN has decided to remove some of the billboards in such a way that there are no more than K billboards standing together in any part of the road.

  You may assume the MG Road to be a straight line with N billboards.Initially there is no gap between any two adjecent billboards.

  ADZEN's primary income comes from these billboards so the billboard removing process has to be done in such a way that the billboards remaining at end should give maximum possible profit among all possible final configurations.Total profit of a configuration is the sum of the profit values of all billboards present in that configuration.

  Given N,K and the profit value of each of the N billboards, output the maximum profit that can be obtained from the remaining billboards under the conditions given.

Constraints
1 <= N <= 1,00,000(10^5)
1 <= K <= N
0 <= profit value of any billboard <= 2,000,000,000(2*10^9)

  My Solution (Psuedocode):

Let Profit[i] denote the Profit from ith billboard.
(i, j) denotes the range of billboards
MaxProfit(i, j) for all (i, j) such that i<=j and i-j+1 <= K is:
    MaxProfit(i, j) = Profit[i] + Profit[i+1] + ... + Profit[j];

For other (i,j) MaxProfit equals,

MaxProfit(i, j)
{
        if(MaxProfit(i, j) is already calculated)
            then return its value;
    max = 0;
    for all k such that i<=k<=j // k denotes that, that position has no   billboard
    {
        temp = MaxProfit(i, k-1) + MaxProfit(k+1, j);
        if(temp > max)
        max = temp;
    }
return max;
}

My solution is of order $$N^2$$. So I get TLE and Segmentation fault for larger N. I have already passed 6/10 test cases. I need to pass remaining 4. Help needed.

You can do it in $O(N \log N)$ time and $O(N)$ space.

Instead of finding the billboards that you want to keep, find the billboards that you want to get rid of.  You need to find the minimum cost set of billboards such that there is no gap of more than $K$ between two billboards. Do this by constructing a table where the $i$th entry is the minimum cost to remove the $i$th billboard and enough previous billboards to make this legal. Now, to add an entry to the table, you need to find the minimum of the previous $K$ entries to the table. You can do this in $O(\log N)$ time using a priority queue.

If $K \ll N$, you might want to use a fancier priority queue that takes $O(\log K)$ time instead; but I'd guess that for large $K$, the simpler priority queues such as heaps that don't admit deletion of a non-MIN item are quicker for this problem. I don't know how tight time limits Interview Street has set for this problem.


Where can I find the data of the computer experiments in the book "Neural Networks and Learning Machines"? The book "Neural Networks and Learning Machines" by Simon Haykin has many computer experiments to which many exercises are related. But there seems to be no data for these experiments available online. Where can I find them?

The MATLAB files for the book are accessible here.
I'm not familiar with the text, but there are .mat files in the zip named

c.mat
sig_lorenz_full.mat

which probably contain the data.  There are also a handful of TIFF files (images) from which he draws the other data.


Randomized agorithm for selecting a $m$-subset out of a $n$-set The question has been discussed here but unfortunately is closed.

Reference : m-element random sample being equally likely ...(CLRS 5.3-7)?

My question is as follows.

Suppose $n = 5, m = 3$. This implies that we need to randomly select a $3$-subset out of $5$ elements. The algorithm makes $3$ recursive calls. The probability of obtaining the set $S_1 = \{1,2,3\}$ is more than that of $S_2 = \{3,4,5\}$ since we can obtain $S_2$ in only one way as follows.

$$ 3 = RANDOM(1,3) \\4 = RANDOM(1,4)\\ 5 = RANDOM(1,5) $$

But in case of $S_1$ we have $3! = 6$ ways of obtaining it, two of them being as follows.

$$ 3 = RANDOM(1,3) \\2 = RANDOM(1,4)\\ 1 = RANDOM(1,5) $$
$$ 2 = RANDOM(1,3) \\3 = RANDOM(1,4)\\ 1 = RANDOM(1,5) $$

Now, how can the output of each $3$-subset is equally likely as claimed in the question?

There are actually only two random steps in this case:

Start with $\{1,2,3\}$.
With probability $3/4$, replace a random element with $4$.
With probability $3/5$, replace a random element with $5$.

You get $\{1,2,3\}$ if you don't insert $4$ or $5$, which happens with probability $$\left(1-\frac{3}{4}\right)\left(1-\frac{3}{5}\right) = \frac{1}{4} \cdot \frac{2}{5} = \frac{1}{10}.$$

You get $\{3,4,5\}$ in two cases:

You replace $1$ with $4$ and then $2$ with $5$.
You replace $2$ with $4$ and then $1$ with $5$.

The probability that you replace a specific element with $4$ is $(3/4)(1/3)=1/4$, and the probability that you replace a specific element with $5$ is $(3/5)(1/3)=1/5$. In total, the probability that we get $\{3,4,5\}$ is

$$ \frac{1}{4}\cdot \frac{1}{5} + \frac{1}{4}\cdot \frac{1}{5} = \frac{1}{10}. $$

So both probabilities are the same.


Directed graph reachability Given a directed graph G(V,E) and a node s, how do we determine what nodes are reachable from s? Do I need simple traversal algorithms or do I need to look at Tarjan's algorithm?

Use depth-first search, or breadth-first search, or any other graph search algorithm.  You don't need Tarjan's algorithm.


What is the relation between universality and chaotic behavior in Elementary Cellular Automata? So i know that rule 110 from Elementary Cellular Automata is universal but i am wondering if we had other chaotic behaviors let's say there exists a system that shows nearly infinite chaotic behaviors {a structure at a time} similar to ECA structures, how can we prove or disprove universality from that system ?

Suppose we have a system with one specific rule to execute and the input can be defined by different number of cells {i.e input = 5 cells} these 5 cells for example can show (2000) chaotic behavior... 4 cells can show nearly (1800), for example to get a structure from the (1800) structures, i can change the 4 cells by changing the rule set of these 4 cells just like in ECA => 'two white cells will result in a black cell', i can define a similar rule set on the 4 cells, 5 cells or more generally on x cells where x < infinite.

That system with same input {4 cells} with different rule set can simulate most of the structures in Elementary Cellular Automata like rule 30, 90 & 60 and others, what can be proved about such system and how universality is related to it ?

Chaotic behavior does not seem to imply universality, from what I can see.  I don't see any reason to expect it would.

For instance, here's an example to challenge your intuition that the two concepts are somehow related.  Wikipedia lists the dynamic system given by the map $x \mapsto 4x (1-x)$ and $y \mapsto x + y \bmod 1$ as an example of a chaotic system.  However I doubt that this system is universal in any meaningful sense.

As David Richerby wrote, the way you prove universality is "by proving that the thing can simulate some other universal system".  I don't think "chaotic behavior" -- whatever that might mean -- is a helpful guide to determining whether a particular system is universal.


Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$? Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$?

If I understand the polynomial hierarchy correctly, then, if $P = NP$, all complexity classes collapse to one class. Therefore the above two classes should also be equal.

The reverse

The reverse is true. If $FP^{NP[log]} = FP^{NP}$ then $P = NP$.

You can quickly find this in the Complexity Zoo; It was proven in
M. Krentel. The complexity of optimization problems, Journal of Computer and System Sciences 36:490-509, 1988.

The actual question

The other way around is easier. To quote the definition from Complexity Zoo:

  $FP^{NP[log]}$: $FP$ With Logarithmically Many Queries To $NP$

Therefore, if $P = NP$, $FP^{NP[log]} = FP^{P[log]}$. Logarithmically many queries to $P$ is certainly a subset of $NP$, so (if $P = NP$) $FP^{NP[log]} = FP^{NP}$.


Is L = {  | M is a TM and L(M)={w}} turing recognizable? And its complement? My approach is to prove that the complement is turing recognizable and undecidable, so that we can prove L not recognizable. But what is the complement of such L?

Intuitively, $L$ is not recognizable as given $\langle M, w\rangle$, to know Whether $M$ accepts $w$ we need to simulate the run of $M$ on $w$, but $M$ need not to halt on $w$, so the simulation may not halt. This obviously smells like the halting problem. Even if we somehow know that $M$ accepts $w$, how can you check whether $w$ is the only word in $L(M)$? What about the other infinite words over $M$'s alphabet? It seems impossible to go over all of these words and verify that all of them are not in $L(M)$ and then halt.
If you consider the complement of $L$, $\overline{L} = \{ \langle M, w\rangle: L(M)\neq \{w\} \}$, you get the same problamatic issue. How can you check whether $L(M)$ does not include $w$?
So intuitively, both $L$ and $\overline{L}$ are not recognizable. Formally, to show that a language $B$ is not recognizable, we show that there a non-recognizable $A$ that reduces to $B$. We consider the non-recognizable language $A = \overline{Halt_{TM}} = \{ \langle M, w \rangle: \text{M does not halt on w}\}$, then we show that there are mapping reductions, one from $A$ to $L$, and the other is from $A$ to $\overline{L}$:

$\overline{Halt_{TM}} \leq_m \overline{L}$: we need to show that there is a reduction from $\overline{Halt_{TM}}$ to $\overline{L}$. Consider the reduction that operates as follows. On input $\langle M, w\rangle$, the reduction outputs $\langle K, w\rangle$, where $K$ is a machine that operates as follows. On input $x$ for $K$, the machine $K$ simulates the run of $M$ on $w$. If $M$ halts on $w$ (if the simulation halts), then $K$ accepts $x$ only if $x = w$, and otherwise $K$ rejects $x$. If $M$ does not halt on $w$, that is the simulation does not halt, then clearly $K$ does not halt.
The reduction is correct: if $\langle M, w\rangle \in \overline{Halt_{TM}}$, then $M$ does not halt on $w$. Hence, $K$ does not halt on any input $x$, and thus $L(K) = \emptyset \neq \{w\}$. Meaning that $\langle K, w\rangle \in \overline{L}$. Conversely, if $\langle M, w\rangle\notin \overline{Halt_{TM}}$, then  $M$ halts on $w$. Hence, $K$ halts on every input $x$, but accepts only if $x = w$, and so $L(K) = \{ w\}$. Thus, $\langle K, w\rangle \notin \overline{L}$.

$\overline{Halt_{TM}} \leq_m L$: we need to show that there is a reduction from $\overline{Halt_{TM}}$ to L. Consider the reduction that operates as follows. On input $\langle M, w\rangle$, the reduction outputs $\langle K, 1\rangle$, where $K$ is a machine that operates as follows. On input $x$ for $K$, the machine $K$ checks whether $x = 1$. If $x = 1$, $K$ accepts. If $x\neq 1$, $K$
simulates the run of $M$ on $w$. If $M$ halts on $w$ (if the simulation halts), then $K$ accepts $x$. If $M$ does not halt on $w$, that is the simulation does not halt, then clearly $K$ does not halt.
The reduction is correct: if $\langle M, w\rangle \in \overline{Halt_{TM}}$, then $M$ does not halt on $w$. Hence, for every input $x\neq 1$ for $K$, $K$ does not halt, and thus $L(K) = \{1\}$. Meaning that $\langle K, 1\rangle \in L$. Conversely, if $\langle M, w\rangle\notin \overline{Halt_{TM}}$, then  $M$ halts on $w$. Hence, $K$ halts on every input $x$ (as when $x\neq 1$, the simulation of the run of $M$ on $w$ halts), and accepts. Hence, $L(K) = \Sigma^* \neq \{ 1\}$. Thus, $\langle K, 1\rangle \notin L$.

Final note: I have assumed w.l.o.g that $\overline{L}$ does not contain words that are not a description of a pair $\langle M, w \rangle$. This is okay, as a reduction (a machine) can easily check whether an input is of the form $\langle \text{ machine, word}\rangle$. If the input of the reduction is not of this form, then the reduction outputs some constant word that is in the language that we're reducing to. So for readability issues, I sticked to this assumption.


Can a subset of an NP-complete problem be in P? The problem is NP-complete (proven) for all input data (without exception).

We assume that P != NP.

Is it possible that there is an (infinitely large) subset of the problem, for which this subset is in P?

Theoretical question.

Your question doesn't make sense:

  The problem is NP-complete (proven) for all input data (without exception).

This is not a thing. NP-completeness is a property of entire sets, not of specific inputs. It's fairly trivial to show that, if you choose a specific input, any problem is $O(1)$ on that input: you just output yes or no, depending which is correct for your input. When you do this, all of algorithm analysis breaks down and everything ends up useless. So, we don't do this.

$P$, $NP$, $NP$-completeness, polynomial time, etc. are all related to asymptotic complexity: as the size of input grows, how does the run-time grow? This only makes sense when you look across different input, the same way the derivative of a point in calculus is a property that takes into account the curve surrounding the point.

  We assume that P != NP.

Again, this doesn't affect your answer. If $P = NP$, then every $P$ set is $NP$-complete,* so there are a bunch of subsets in $P$. And if $P=NP$, the examples that people have given are all valid.

  Is it possible that there is a subset of the problem (infinitely large), that this problem is in P?

Yes, and the other answers have given great examples of this. But for posterity, here's yet another counter example.

$k$-coloring is $NP$-complete if you take $k$ as input, but $2$-coloring is an infinite subset of this that is in $P$.

* Except for $\emptyset$ and $\Sigma^*$, which aren't $NP$-complete for technical reasons relating to the form of reductions we use to define completeness.


Cannibals missionaries problem - solving usings graphs I am trying to solve the cannibals - missionaries problem; we have the number of cannibals, the number of missionaries and the position of the boat. We are trying to transfer all of them to the other side, however there can't be more cannibals than missionaries on either side. The capacity of the boat is limited by 2.

There are multiple ways to solve this problem, I'm trying to do it using graphs. My questions is, how to I transform these "states" (M,K,B) into vertices in a graph? Each state represent the number of missionaries, the number of cannibals and the position of the boat.

I'm having troubles with visualization of these practical problems into graphs. Could you give me any help on how to add those vertices to the graph? Once I have the graph completed, it should be easy to solve using BFS.

You did most of the job. Each vertex is a state $(M, K, B)$ and edges represent the possibility to pass from a state to another with one ship transport. Let say $B$ can take the values $L$ or $R$ for left and right edges respectively. $K$ is the number of cannibals on left edge and $B$, the number of monks on left edge. Initially all monks and cannibals are on left edge with the boat: state is $(M_0, K_0, L)$. Note that for any state there are $M_0-M$ monks and $K_0-K$ cannibals on right edge.
You can notice that any ship transport would change $B$ value from $L$ to $R$ or vice-versa. Thus your state graph is a bipartite graph. It changes nothing to the problem, but it is interesting to notice it.
Concerning $K$ and $M$, to respect the "cannibal constraint", a valid node must have:

$K \le M$ for left edge (or $M = 0$),
$K_0-K \le M_0-M$ for right edge (or $M=M_0$)

A valid left->right transport (edge) should be:
$(M_i, K_i, L)$ -> $(M_i-m, K_i-k, R)$, such that $(m, k)$ in $\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\}$.
and a valid right->left transport (edge) should be:
$(M_i, K_i, R)$ -> $(M_i+m, K_i+k, L)$, such that $(m, k)$ in $\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\}$.
Of course you must keep $0 \le M \le M_0$ and $0 \le K \le K_0$.
BFS in the graph
So now, how to proceed ? You can create all possible vertices that is to say all $(M, K, B)$ with $M \le M_0, K\le K_0, B \in {L, R})$ that does respect the cannibals constraint. Then build all the possible edges (up to 5 from any vertex). Finally you can run the BFS in this graph to find an eventual solution. The graph would have up to $2 M_0 K_0$ vertices and $10 M_0 K_0$ edges.
A stronger solution is to build your graph as you explore it. You can express formally all states reachable from any state and check if the vertex of this state is already explored or not.
Also note that BFS is generally a good exploration method to find the shortest distance, but here you can expect left->right transports should move 2 persons and right->left transports should move only one person to decrease the left edge population.
This is indeed a good exercise for graph state representation and exploration, but after it you should try to answer these questions:

What property between $M_0$, $K_0$ is necessary and sufficient to have a solution ? (exception of $M_0 = 0$)
What is the straight forward method to find such solution ?

Here is a small example for $M_0 = 3, K_0=2$. In blue the edges enconutered and in red the followed one.


When inserting into a binary tree, is there a universal agreed upon place to insert then new node to minimize complexity? Do programmers (in real life), always insert at the top node or somewhere else? Because in my text book CLRS it is not made very clear, so the insertion process can take a best case of O(1), if you insert it just at the right place, or a worst case when you have to rebalance the entire tree.

So in practice is there a place that all new nodes are inserted?

There are several different concepts here. Let's start from the most general. A tree is a data structure that consists of a root and a collection of children, each of which is a tree. A node of the tree is either the root of the tree itself of a node of the children, i.e. it's the root, or the root of a child, or the root of a child's child, etc. The nodes of a tree can contain information of any type. Here are a few examples of trees:

One that you encounter everyday when working with computers is the filesystem¹: there's a root directory, subtrees are subdirectories, and there are subtrees which have no children and which are regular files; the children of a node are identified by a name (so it's not “first child”, “second child”, etc. but “child named hello.txt, child named pictures”, etc.).
An example from real life is the section structure of a book: there's the book, which is divided into chapters, which are divided into sections, which are divided into subsections, etc.
One type of tree data structure is the trie, which stores information indexed by a string. Each node has one child per character in the alphabet. The information corresponding to a string is located by starting from the root, going to the child corresponding to the first character of the string, then to the child of that child corresponding to the second character, etc. For example the string abc would be stored three levels deep, going down from the root to the a child, then to its b child, then to its c child.

You'll notice that in the filesystem and in the book sections example, information can be inserted anywhere. I can store my files in whichever directory I want; I can add a section to the chapter of my choice. In contrast, the structure of a trie is completely rigid: there's only a single place in the tree where abc can go.

A binary tree is a tree where each node happens to have at most two children. The two children are typically known as the left and right child. There is a common variation on this definition that defines a binary tree to have two types of nodes: internal nodes which must have exactly two children, and leaves which have no children.

A binary search tree is a type of tree data structure. Like a trie, it imposes a constraint on where the information must be stored. A trie indexes information by a string; a search tree indexes information that is ordered: it can be numbers, strings, etc. In a binary search tree, the data in the left subtree of a node is always smaller than the datum in the node itself, and the data in the right subtree of a node is always smaller than the datum in the node.

If you try to add element into an existing search tree, there's a single way to do that without changing the current structure of the tree: going down from the root, take the left child if the node is larger than the element to add, take the right child if the node is smaller, and keep going until you get to a child that doesn't exist, and create that child.

However, the structure of search trees is less rigid than the structure of tries: there are different search trees that contain the same data. For example, here are three binary search trees containing the integers 2, 4, 5, 8, 9 (there are of course many more):

      8            4          2
    /   \         / \          \
   4      9      2   5          4
  / \               / \          \
 2   5             8   9          5
                                   \
                                    9
                                   /
                                  8

In the worst case, inserting an element in a search tree requires traversing the whole height of the tree, which as the last example above show can be as much as the number of elements of the tree.

The leeway in the tree structure allows one to reshape the tree when adding or removing elements from it. This is called balancing. Balancing is done in order to keep the height small, which keeps operations such as search, insertion and deletion efficient. There are several variants of balanced search trees, where the balancing operations is designed to keep the height of the tree logarithmic in the number of elements of the tree: $h = O(\log(n))$. The basic principle of a balanced search tree is to keep some information about the height of the subtree in each node; when the height difference between the two children of a node is too large, some nodes are moved from the deeper subtree to the shallower subtree to rebalance. The rebalancing operation costs $O(1)$ at each node and is performed over the path to the element that's being inserted or removed, so its cost over the whole tree is $O(h) = O(\log n)$. This way, search, insertion and deletion in a balanced search tree cost $O(h)$ to find the target location, plus $O(h)$ to rebalance, which is $O(h) + O(h) = O(\log n)$ total.

¹  In practice filesystems can be more complex than what I'm talking about here. Filesystems with hard links aren't even trees.


Binary Integer Programming question - what graph problem is represented I'm dealing with a BIP question, that represents a graph problem.
The goal is finding the graph problem.

I've spend a lot of time trying to solving this question but I couldn't find the answer to that question.

All I'm given is the set of constraints and the objective function:

I'd really appreciate your help, no full answer needed, just a direction.

$$
\begin{align*}
\min & \sum_{ijk} z_{ijk} c_{ij} \\
\text{s.t.}\; & \sum_j x_{ij} = 1 \qquad \forall i=0\ldots n-1 \\
& \sum_i x_{ij} = 1 \qquad \forall j=0\ldots n-1 \\
& z_{ijk} \geq x_{ik} + x_{j(k+1\,\mathrm{mod}\,n)} \qquad \forall i,j,k=0\ldots n-1 \\
& x_{ij},z_{ijk} \in \{0,1\}
\end{align*}
$$

This answer assumes that $c_{ij} \geq 0$.

The first two sets of equations guarantees that $x_{ij}$ is a permutation matrix. It defines a permutation $\pi$ on $\{0,\ldots,n-1\}$ in the following way: $\pi(j) = i$ if $x_{ij} = 1$.

The set of inequalities is a logical implication: if $x_{ik}=x_{j(k+1)}=1$ then $z_{ijk} = 1$. That is, if $\pi(k) = i$ and $\pi(k+1) = j$ then $z_{ijk}=1$.

Since $c_{ij} \geq 0$ and the objective is to minimize $\sum_{ijk} z_{ijk} c_{ij}$, we want to have $z_{ijk} = 0$ unless we are forced to take $z_{ijk} = 1$. Therefore $z={ijk} = x_{ik} \land x_{j(k+1)}$. This means that the objective function is
$$
\min_\pi \sum_{k=0}^{n-1} c_{\pi(k)\pi(k+1)}.
$$
This is the problem known as minimum directed Hamiltonian circuit.


Algorithm to schedule employees into days I'm trying to build a scheduling app for a friend, but am stuck on how to sort the employees.
I have three holidays each with their own employee_need:
thanks_giving: 2
christmas: 3
new_years_eve: 2
I have employees who have a predetermined number of days they will work. The sum of the employee’s predetermined work days will always add up to the sum of the three holiday’s employee_need. They also have ranked the holidays by preference, which should guide the scheduling process.
The data looks something like this:
Polly:
days_to_work: 1
preferences: [christmas, new_years_eve, thanks_giving]
Stan:
days_to_work: 2
preferences: [thanks_giving, christmas, new_years_eve]
etcetera.
Right now my process of sorting is to

Fill each holiday with a list of all employees.

Loop through the employees, starting with those who have the most days off.

Loop through the employee's preferences and pull them from the one they most desire to have off that also has room for them to be taken off

Continue looping until the days are properly scheduled.  If there is room to remove them from that day, I do so, until they are working the number of days they are supposed to.

The algorithm works a decent amount of time, but I really need it to work all the time.
Is anyone familiar with this kind of problem, and can point me toward a better methodology?

This looks a lot like the stable marriage problem, itself related to the problem of matching in biparftite graphs. There are very efficient algorithms to solve both problems.


Universal queue automata Does anyone know whether universal queue automata have ever been considered, and, as for Universal Turing Machines, some "small" universal queue automata are known?

Well, a very similar concept, called Tagsystems is an early universal model developed by Post. Here is the description from wikipedia:

  A tag system is a deterministic computational model published by Emil
  Leon Post in 1943 as a simple form of a Post canonical system. A tag
  system may also be viewed as an abstract machine, called a Post tag
  machine (not to be confused with Post-Turing machines)—briefly, a
  finite state machine whose only tape is a FIFO queue of unbounded
  length, such that in each transition the machine reads the symbol at
  the head of the queue, deletes a constant number of symbols from the
  head, and appends to the tail a symbol-string that depends solely on
  the first symbol read in this transition.

It is explained in the introductory part of a paper by Woods and Neary for FOCS 2006 that small universal TM's are actually built from small universal Tag-systems. Hence there is a big competition in finding small Tag-systems.


What does it mean to "strengthen the precondition and weaken the postcondition" in Hoare logic? Having learned a rough summary of Hoare logic (i.e. learning just the basic concept of Hoare triples and a few of the rules) I kept seeing a statement along these lines:

  The rule of consquence allows us to strengthen the precondition and weaken the postcondition. (paraphrased)

What does it actually mean to strengthen the precondition and to weaken the postcondition?
Is and used in its strict logical meaning in this sense, i.e. if we apply the rule of consequence we will always do both? Or can it be read as allowing us to choose to strengthen the precondition or weaken the postcondition?

I get the (very basic) idea of the rule, but this statement implies the rule can be applied for a strategic reason that isn't clearly explained.

Thanks.

Condition $A$ is stronger than condition $B$ if $A$ implies $B$.  That is, if $B$ holds in all situations in which $A$ holds.  Conversely, if $A$ is stronger than $B$, then $B$ is weaker than $A$. Note that, from the definition, $A$ is stronger and weaker than itself, since $A$ implies $A$.  (We might prefer to say "at least as strong as" instead of "stronger than" but I guess that gets convoluted and it's easier to just remember that "stronger than" really means "at least as strong as".)

So, to strengthen a condition is to replace it with a stronger one; to weaken a condition is to replace it with a weaker on. Because a condition is always stronger and weaker than itself, the phrase "strengthen the precondition and weaken the postcondition" does indeed mean that we can leave one (or even both!) of them unchanged.


Which hazards are solved by instruction reordering? I am not clear on whether it's data and control hazards, or control hazards only. Also, the "solved" word confuses me - technically, instruction reordering is used to solve dependences and thus prevent hazards from happening in the first place. Once they do happen, though, it's stalls and forwarding. Would that make the answer "None"?

Is my thinking wrong?

Instruction reordering in cpu-pipelines doesn't solve any hazards problem.

Register renaming eliminates write-after-write data hazards on registers and write-after-read data hazards on registers.

Speculative execution tries to find some useful work to do in the presence of control hazards.

Instruction reordering only works between instructions that are already completely independent of one another (either because they work with completely different registers or because after register renaming they don't need any of the same registers).  At best I would say that instruction reordering solves a "bookkeeping hazard" (I just made that term up).  The reason you would not do instruction reordering dynamically in the pipeline is if the bookkeeping hardware to do instruction reordering is too expensive for one reason or another.  Issuing instructions in-order is cheaper (in terms of hardware) than implementing the queues and logic to do out-of-order issue.


Is there a generally agreed short notation for "a points to b" Is there a conventional symbol for "points to" or "is a pointer to". I've been using a short right arrow; for example "a is a pointer to b" would be (approximately)

a -> b

but I wonder whether a short double right arrow would be better:

a => b

Best of all would be to know, and use, a universally-accepted standard symbol, if there is one?

The problem with your question is that pointers and pointers semantics
may vary significantly from language to language. Even your question
is ambiguous. So you are asking a question about notation, i.e., about
syntax, which is largely a matter of arbitrary convention, but it is
not even clear what is the semantics intended by your question.

You apparently use as synonyms "a points to b", "a is a pointer to b",
"a -> b". But I am not sure what is the meaning and context. Does it
assert that a is actually pointing to b (descriptive meaning) or
does it modify the data so that a is now pointing to b (imperative
meaning). Then what is b, or what can b be. Is it the location of
some value, or is it the value of whatever is pointed by a. Is it
intended to be part of a programming language syntax, or of the
metalanguage used to discuss about programs.

If you have a -> b and c -> b, does it imply that a = c. Furthermore, if a and c are pointers, what is the meaning of
a = c? See for example "shallow and deep equality".

Actually all this is often an issue of designation of container and
content. A pointer is a designation for a container (a memory
location, for example), and the content of that container may vary.
But the content may also include container designation.

One major problem is that notations are often ambiguous as they often
do not clearly distinguish between container and content, often implicitly
casting one into the other.

If you consider a variable, say an integer variable x in some
programmning language, this variable is actually a container where you
can change the content (which is supposed to be an integer). But,
within the scope of its declaration, x will always be the same
container. An integer variable is actually a pointer constant: a
location designator.

Then, can you write x -> 3 to indicate that x denotes a pointer
constant toward a location containing the value 3?

Or is the arrow supposed to point on the right to whatever container
is "designated" by the expression on the left. But if you have a
pointer constant (i.e. a pointer value) on the left, what is the
meaning of the notation.

Now, you can have pointer variables, which may contain a
container. They can appear through explicit declaration, or via other
mechanism such as parameter passing by reference.

When sharing a meal with other people, you can ask for the bottle or
for the wine. It will mean the same. But in programming context, more
precision may be needed.

So my first reaction to your question is: Could you be more precise
about the semantics you intend to express, before you suggest agreeing
on a standard notation?

Another minor point is that, while asking your question, you seem to
suggest that a double shafted arrow => would be better than a single
shafted on ->. But you do not give any hint as to why it might be
better. This makes me uneasy, especially wen I am not even sure of
what you want to talk about, and in what context.

Since this is supposed to be an answer rather than further questions,
I would suggest that the lack of a standard may well come from the
fact that programming languages vary significantly in their use of
pointers, and on the semantics attached to various constructs using
pointers. We can hardly standardize notation when what is to be denoted is
not itself standardized.

Hence, our only recourse is to choose for ourselves a notation that is intuitive and
consistent in its intended context, and define it precisely together
with the associated semantics. I insist on consistency since there are
many things you may want to do with pointers, and it is important
that the notations for each remain intuitive, and that they combine
naturally and consistently. The issue of equality is an example.


Why would you use a monitor instead of a semaphore? I am currently attending the concurrent programming course in my university and we recently started talking about the concept of a monitor. While I understand the necessity of mutual exclusion, I do not understand why I would use a monitor for that.

As I understand it, a monitor guarantees that exactly one or no process is in the critical section at all times. We can achieve exactly that with a semaphore. Furthermore we implement monitors (or at least one possibility to implement them is) with semaphores.

So why would I implement something that does exactly the same thing as a semaphore with a semaphore? What benefits do I get?

They are nearly interchangeable and one can be built out of the other. It is somewhat language dependent which is implemented/ preferred (eg Java has built-in monitors using "synchronize" keyword). However the semaphore is considered a "lower level" entity than the monitor for the following reasons & differences:

Both Monitors and Semaphores are used for the same purpose – thread synchronization. But, monitors are simpler to use than semaphores because they handle all of the details of lock acquisition and release. An application using semaphores has to release any locks a thread has acquired when the application terminates – this must be done by the application itself. If the application does not do this, then any other thread that needs the shared resource will not be able to proceed.
Another difference when using semaphores is that every routine accessing a shared resource has to explicitly acquire a a lock before using the resource. This can be easily forgotten when coding the routines dealing with multithreading . Monitors, unlike semaphores, automatically acquire the necessary locks.[1]

See also the highly voted Stack Overflow answer Semaphore vs. Monitors - what's the difference? with a great/ memorable analogy to public toilets & bike stands.


Real-valued genetic algorithm offspring out-of-bounds I have a fairly simple real-valued genetic algorithm that seems to work fairly well, however it currently has some issues that I'm hoping to get some help with. If we consider a 1-dimensional problem, I use the following method to produce 3 children/offspring $(c_{1,2,3})$ from 2 parents $(p_{1,2})$:
$$c_{1} = 0.5p_{1}+0.5p_{2}$$
$$c_{2} = 1.5p_{1}-0.5p_{2}$$
$$c_{3} = -0.5_{1}+1.5p_{2}$$

For example, if we consider a problem where the bounds are $0\leq x\leq 10$, and I have 2 parents with $x$-values given by $p_{1} = 2.55$ and $p_{2} = 9.92$, then we produce 3 children with the following $x$-values:

$$c_{1} = 6.235$$
$$c_{2} = -1.135$$
$$c_{3} = 13.605$$

As can be seen, child 1 will always be within the problem bounds since it's simply an average of its parents, however children 2 and 3 have $x$-values that are outside the bounds of the problem $(0\leq x\leq 10)$. As such, what I then do is simply have a loop that adds 1 to the value of child 2 and subtracts 1 from the value of child 3 until they go back within bounds, and then carry on with the rest of the algorithm. But this seems like a "cheap trick". As such, I was wondering if better methods are used to deal with children/offspring that have values outside of the problem bounds, or if my method is actually acceptable.

Anything is acceptable.  These are all heuristics; all that matters is results (i.e., whether it helps you find a good solution to the problem, and how quickly it does so).

One standard method is to "clip" all values to be within the bounds.  In other words, if the value is smaller than 0, you replace it with 0; if it is larger than 10, you replace it with 10.  This ensures that the value will be within bounds.

There are other methods as well.  For instance, you could let $y = 10 \sigma(x)$ where $\sigma(x) = 1/(1+e^{-x})$.  You apply genetic programming to the values $x$ (so you do mutation and crossover operations on the $x$ values), but then you calculate $y$ and use that as the actual output.  Note that $x$ can be any real number ($-\infty < x < \infty$) and the definition of $y$ will ensure that $0 \le y \le 10$.


Question on pseudocode for Ford-Fulkerson in Kleinberg-Tardos Text I am looking at the following pseudocode from the Kleinberg-Tardos text "Algorithm Design".

Max-Flow
Initially f(e)=0 for all e in G
While there is an s-t path in the residual graph G_f
    Let P be a simple s-t path in G_f
    f' = augment(f,P)
    Update f to f'
    Update the residual graph G_f to be G_f'
Endwhile
Return f

This seems to make sense to me. However, prior to displaying this pseudocode, the textbook gives pseudocode for the augment subroutine:

augment(f,P)
Let b = bottleneck(P,f)
For each edge (u,v) in P
    If e = (u,v) is a forward edge then
        increase f(e) in G by b
    Else ((u,v) is a backward edge, and let e = (v,u))
        decrease f(e) in G by b
    Endif
Endfor
Return(f)

Unfortunately, the textbook does not give any implemenation details on the bottleneck() subroutine.

But what I cannot understand is why we would need to pass the flow function $f$, to the bottleneck subroutine?

It seems that the bottleneck routine is looking at a simple s-t path in the residual graph $G_f$. Hence bottleneck is only concerned with the residual capacity along each edge. When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity. Hence, a call such as bottleneck($P$) would seem to suffice which simply looked for the minimum capacity along the edges in $P$.

Can someone shed any light on why we pass $f$ to this bottleneck subroutine?

This is pseudocode, not the end-all be-all of the algorithm implementation. It is a very high level overview and by nature is left up to interpretation for the implementation. That being said...

  "When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity."

This is not necessarily the case. You can analyze the residual graph in place, simply based on $f$ and $G$. By this, I mean it is not necessary to explicitly create a new graph $G_f$ because $G_f$ is merely a function of $G$ and $f$.

If this is the case, then the flow function $f$ is passed in to compute the residual capacity of each edge in the path. Similarly to how $G_f$ can be computed in place, if we have a path $P_f$ (from $s$ to $t$) in $G_f$, it doesn't necessarily have to an explicit path in $G_f$. It could be a path in $G$ for which we must compute $P_f$. This is when we might require $f$ to compute the bottleneck.

Again, this is just pseudocode and if you implement in a slightly different way than is described, that's okay as long as the procedure is correct.


Applying the context-free pumping lemma to a language with crossed nestings For proving language $\{a^nb^mc^nd^m \mid n,m > 0\}$ is not context free.
Do I have to use $z = a^pb^pc^pd^p$ as pumping lemma string where $p$ is pumping length?

Or do I have to use a string that would reflect than $n$ and $m$ does not have to be the same length?

Pumping lemma lets you construct new strings belonging to the context-free language.

To prove that the language is not context-free you can take some string $s$ from L, use pumping lemma to construct a new string $s1$ which must belong to $L$ (because you used pumping lemma to construct it!). Then you show that $s1$ does not belong to L => contradiction.

Choice of original $s$ is yours. So yes, you can use $z = a^pb^pc^pd^p$ in your proof.


Finding the rows/columns of an m-by-m symmetric similarity matrix M which minimizes the sum of the elements in an n-by-n submatrix N, where n < m I have a machine learning problem where I need to find the most dissimilar subset of rows/columns of an $m$-by-$m$ symmetric similarity matrix $M$ which minimizes the sum of the elements in an $n$-by-$n$ submatrix $N$, where $n < m$. In other words, by minimizing this sum, we find the most dissimilar rows/columns in $M$ that makes up $N$.
The values of $M$ are real, positive values between zero (dissimilar) and ones (similar). The diagonal consists of ones as the diagonal compares the same object with itself, meaning they definitely are identical. Furthermore, as the matrices are symmetrical, selecting row $i$ from $M$ also includes selecting column $i$ from $M$ (for $N$).
Take a 3-by-3 matrix as an example (i.e. $M$ with $m=3$):
\begin{pmatrix}
1 & 0.8 & 0.2 \\
0.8 & 1 & 0   \\
0.2 & 0 & 1
\end{pmatrix}
In this case, the first and second element are relatively similar (0.8), first and third are relatively dissimilar (0.2), and second and third are completely dissimilar (0). Assuming $n=2$, there are three possible ways to construct the submatrix $N$:

Select first & second row/column:

\begin{pmatrix}
1 & 0.8 \\
0.8 & 1
\end{pmatrix}

Select first and third row/column:

\begin{pmatrix}
1 & 0.2 \\
0.2 & 1
\end{pmatrix}

Select second and third row/column:

\begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}
For this particular case, we know that the third alternative minimizes the sum. However, scaling this problem to $m=5000$ and $n=400$ makes the problem impossible to compute as the number of possible submatrices gets insanely large.
I was initially considering using the Monte Carlo method, but I'm thinking that there might be a more elegant way to do this. Do you have any pointers?

Unfortunately this problem is NP-hard, meaning the best exact algorithm you can hope for will take exponential time in the worst case.
It is NP-hard because any algorithm that would solve this problem can also be used to solve the NP-hard problem Independent Set (IS), in which we have a graph $G = (V, E)$ and an integer $k$, and ask whether there is a subset $X \subseteq V$ of $k$ vertices such that no pair of vertices in this subset are adjacent. Given any algorithm for solving your problem, any instance $G$ of IS can be solved by giving this algorithm the adjacency matrix for $G$, in which every element is 1 (indicating a pair of vertices connected by an edge) or 0 (indicating a pair of vertices that are not) as input, together with $N=k$; there is a size-$k$ independent set in $G$ if and only if there is a subset of $N$ rows/columns in the matrix having sum $N$ (i.e., all diagonal elements are 1 and the rest are 0).


how to mapping reduce any r.e. language to the diagonal language K? We know that the halting problem $A_{TM}$= $\{(e,x) \mid M_e(x)$ accepts$\}$ and the diagonal language K= $\{e \mid M_e(e)$ accepts$\}$ are mapping reducible to each other. Recall that A mapping reducible to B means there exists a computable function from A to B s.t. for all x in A, x in A iff f(x) in B. Furthermore both are complete with respect to this mapping reduction relation.

I would like to prove that any r.e. language is mapping reducible to K directly without reducing to ATM. How can this be done?

For any r.e. language $L$, it is the domain of some M_l.

Consider the machine $M_n(x,y)=M_l(x)$, and now let $f(x)=s_1^1(n,x)$ (obtained from snm theorem). Hence for any $y$, $M_{f(x)}(y)=M_l(x)$

Then $L$ can be reduced to $K$ by $f$ :

if $x\in L$ iff M_l(x) halts iff $M_{f(x)}(f(x))$ halts iff $f(x)\in K$.


Data structure for sparse matrices for an online problem I need to compute a large linear optimization problem very often after recieving updates to my optimization problem.

That is I have a linear problem to find an x such that

$x_1 * c_1 + ... + x_n * c_n$ is as small as possible

under the conditions that $Ax \# b$ (where $\#$ can be $<=$, $>=$ or $=$ on each row).

At some (small) time interval the $a_{ij}$, $c_i$ and $b_i$ can get updates and I need to recompute. The updates only touch very few of the entries and most of the time the changes are only by small amounts.

Some of the $x_i$ are integer variables, some are binary variables and some are real variables.

Current idea:

find a sparse matrix data structure which allows for efficient updates
implement a branch-and-bound algorithm which works on that data structure

Question: which combination of sparse matrix representation and linear optimization algorithm is the current state of the art for such a problem?

Sub-question: is there a way to use the result from the previous run if I know only a few entries change?

In low dimension, Seidel's algorithm can be useful: if we have the optimal solution to $m$ constraints in $d$ dimensions, and you add one more constraint, then the amortized cost to find the optimal solution to those $m+1$ constraints is $O(d!)$, assuming the constraints are being presented in a random order.

(It is usually presented in the following form: if we have $m$ constraints, and we add them one-by-one, updating the optimal solution after each constraint is added, then the total running time to do this is $O(d!m)$ using Seidel's method.  But that's equivalent, if we assume constraints are added in a random order.)

In high dimension, I don't know of any good method.  There is a trivial observation that if $x^*$ is the optimal solution to the constraints, and we add a new inequality, and $x^*$ satisfies this new inequality, then $x^*$ remains the optimal solution, so there's no need to re-solve the LP.  This condition can be tested in $O(d)$ time.  However, if $x^*$ doesn't satisfy the added inequality, I don't know if there's anything better you can do than solve the new LP from scratch.  Same for changing or removing an existing inequality, or changing the objective function.

I'm not sure your question about data structures is well-defined.  Data structures are chosen based upon the set of operations you intend to perform on them.  In this kind of problem, it's usually the algorithm that is the more important part.  You start with the algorithm, then choose a suitable data structure.  But my impression is that with LP, the hard part is the algorithms, and the data structures tend to be comparatively simple.  So asking about sparse matrix data structures  for your problem seems to be putting the cart ahead of the horse.


Would the P vs. NP problem become trivial as a result of the development of universal quantum computers? If someone were to build a universal quantum computer, would that have any implications on the problem of P vs. NP?

No, there will be absolutely no implication, for several reasons:

The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard problems in polynomial time (which we don't expect them to be able to do), it could still be the case that classical computers cannot solve them in polynomial time.
Universal quantum computers, in a theoretical sense, are (to the best of my knowledge) already known to exist. These are just the quantum analogs of universal Turing machines: they can execute any given quantum "program".
Both quantum computation and the P vs. NP problem are theoretical notions. What someone can construct in the physical world has absolutely no bearing on anything having to do with them.

Lieuwe Vinkhuijzen gave a different interpretation of your question:

  Will quantum computers be able to solve NP-complete problems efficiently?

The expected answer is: no. So even in this sense, physical quantum computers won't enable us to solve NP-complete problems at will.


Turing machine - compare two words I have a simple turing machine with single tape.
I need to compare two words <w1>$<w2>$ and write output.
Language is all letters and numbers.

I did comparation with the {a,b} language but there are more characters.

Is only solution do it one by one in different branches? I mean read / mark the letter (enter the letter branch), go to the second word and read /mark the same letter, go to the first word, repeat?
My problem with this solution is, when I want to change something I need to remake all branches. The other problems are the error handling, when I do not find the right letter I don't want crash. How handle that?

Yes, running back and forth comparing letters is the best you can do. You could always read and remember two, three or any fixed amount of symbols at a time; then there would be less running back and forth, but the programming would be even worse.

And yes, in general you have to rewrite everything when you change something. There are no functions, procedures etc. that you can program in a modular way. In principle, though, you could use different, disjoint sets of states in different parts of your computation. If you change something in one part, you only need to adapt the "interface" where you move from one set of states to another.

If you do not find the right letter, in principle there is no problem with "crashing", because this probably means not accepting. If you want a "controlled" end, you can for example run to the right end of the input and stop there (stopping means entering a configuration where no more move is possible); if this kind of stopping for you is "crashing" you can also enter into an infinite loop.


How many segmentations are possible for a string length N? I have a string with length N. I would like to know how many segmentations are possible to it.
Consider the example abcdc the number of N = 5
All possible segmentations are

['abcdc']
['abcd', 'c']
['abc', 'dc']
['abc', 'd', 'c']
['ab', 'cdc']
['ab', 'cd', 'c']
['ab', 'c', 'dc']
['ab', 'c', 'd', 'c']
['a', 'bcdc']
['a', 'bcd', 'c']
['a', 'bc', 'dc']
['a', 'bc', 'd', 'c']
['a', 'b', 'cdc']
['a', 'b', 'cd', 'c']
['a', 'b', 'c', 'dc']
['a', 'b', 'c', 'd', 'c']

Then what will happen  when  my N tends to infinity . Any closed form equations?

There are n-1 points where you can break the string. Each is independent of the others. Therefore there are $2^{n-1}$ possibilities to break the string.


Algorithm for this problem on generating all permutations I am trying to come up with an efficient algorithm to solve the following problem but not able to design anything nice. I am encountering this problem for a project I am pursuing. Following is an abstracted version of the problem so that I don't confuse anyone with the specifics.

The problem is like this:

I have a list of groups. each group might have an arbitrary number of elements with some weight in it. A valid vector comprises of exactly one member from each group and has members from each group in the list. The weight of a vector is the product of weights of the members in the vector. I want to find the sum of weights of all valid vectors.

for example:

Group 1:
Member 1, Member 2

Group 2:
Member 3

Valid Vector 1:
Member 1, Member 3

Valid Vector 2:
Member 2, Member 3

We need to find:
(Member 1 * Member 3) + (Member 2 * Member 3)

The groups don't intersect. Which means a member can belong to only one group.  What I am doing currently is a brute force like solution, where I start with creating a global list and populating it with the members of group 1. I then go to the next group (group 2) and extend the global list by multiplying each member of group 2 with each member in the global list. Thus completely replacing global list with all pairs of members from group 1 and group 2. In this manner, I keep extending the global list till I have processed all groups.

Suppose that there are $n$ groups, that group $i$ has the $m_i$ elements $x_{ij}$. It is a nice exercise to show that the sum of weights of all valid vectors is
$$ \prod_{i=1}^n \sum_{j=1}^{m_i} x_{ij}. $$
(In you example, you can factor your formula as (Member 1 + Member 2) * Member 3.)


Context Sensitive Grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$ I have been trying to find a context sensitive grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$ for some time but I cannot get it done. Any ideas ?

In the following grammar the first block of productions ensures that the right amount of $a,b,c$, and $d$ is generated, in some order. The terminal  $a$ is represented by the nonterminal $A$, $b$ by $B$, etc.
They also ensure that $X$, which represents a $a$, is at the end of the sentential form.

The next block ensures that $A,B,C,D$ can be reordered.

The last block ensures that terminals are generated from right to left in the correct order (first $d$, then $c$, then $b$, and finally $a$).

$$
\begin{align*}
S  &\to ABBCCCDS'X \\
S' &\to AABBCCCDS' \mid BDDD\\
\\
BA & \to AB \\
CA & \to AC \\
CB & \to BC \\
DA & \to AD \\
DB & \to BD \\
DC & \to CD \\
\\
DX &\to Xd \\
X &\to Y \\
CY &\to Yc \\
Y &\to W \\
BW &\to Wb \\
W &\to Z \\
AZ &\to Za \\
Z & \to a
\end{align*}
$$


Is it possible to balance a already constructed un-balanced AVL tree, with no prior information of last insert? Im learning about tree data structures, and had a question that i couldnt find answer to so I came here.

Usually when we balance a tree, we insert keys and keep checking balance factor, as soon as it exceeds the given limit of (-1,0,1) we immediately balance it and continue to insert keys, if any.

But lets say, I construct a tree, and I dont check balance factor after each key is inserted and I just completely construct the tree first and then I calculate balance factor for each node and attempt to balance the tree.

Q) Is it possible to balance tree using such approach ? If yes, then how?

Q) If no, then why not? What would be the flaws/problems that would arise using such approach ?

What you are asking is simply how to balance a binary search tree (BST) $T$. By the way, the phrase "un-balanced AVL tree" is somewhat confusing since AVL tree is height balanced by definition.

If there is enough space for a whole new tree, then we can simply construct a new AVL tree from scratch, by removing one element from the $T$ and inserting it to the new tree repeatedly. You may call this cheating. While I would agree with you if I were on your side, I can also argue this is just an alternative simple way of balancing a BST, although slightly revolutionary and possibly heavy. Note that we can improve the performance of this approach by taking advantage of the fact that $T$ is a BST, as shown in the exercise 2 below.

Suppose we do not have that much space. Here is how we can balance $T$ in-place. Count the number of nodes in the left subtree of the root node and the number of nodes in the right subtree of the root. If their difference is greater than one, then let us find $m$, the median node of all nodes when the number of all nodes is odd or one of the two median nodes of all nodes when the number of all nodes is even.

Suppose $m$ is the left child of its parent node. Consider $R$, the right subtree of $m$ and $T'$, which is $T$ with the subtree with root $m$ removed. Note that all nodes of $R$ is smaller than all nodes of $T'$. So we can merge $R$ and $T'$ into a new BST $T''$ easily in $O(1)$ operations. Now set the right subtree of $m$ to $T''$ and set $m$ to be the root.
Otherwise $m$ is the right child of its parent node. This case is symmetric to the above case.

Now we have obtained a BST tree whose root is a median of all nodes. Repeat the process above on its left subtree and right subtree, as long as the subtree has more than 2 nodes. In the end, we will obtain a BST where the difference of the number of nodes in the left subtree and the number of nodes the right subtree of any node is at most 1. Let us call this kind of BST "optimally-balanced". Intuitively and apparently, you cannot make a BST more balanced than an optimally-balanced BST. It is not hard to prove that an optimally-balanced BST must be an AVL tree.

I might have skipped over a few boundary cases and a few finer points in the above explanation. Hopefully, the above is able to convince you that the answer to "is it possible to balance an already constructed 'un-balanced AVL tree'" is positive once you have taken some time to reflect.

Here are several related exercises that you can think about. $T$ is a given BST with $n$ nodes.

Exercise 1. Show that an optimally-balanced BST must be an AVL tree.

Exercise 2. If there is enough space, convert $T$ to an AVL tree in $O(n)$ time.  (Hint, convert $T$ to a sorted array first.)

Exercise 3.  With $O(1)$ working space, balance $T$ into an AVL tree in $O(n)$ time. (This might be a difficult exercise.)


how 16 bits address lines address 64KB? " The 8080 was an 8-bit CPU, meaning it processed 8 bits of information at a time. However, it had 16 address lines coming out of it. The ‘‘bitness’’ of a CPU—how many bits wide its general-purpose registers are—is important, but to my view the far more important measure of a CPU’s effectiveness is how many address lines it can muster in one operation. In 1974, 16 address lines was aggressive, because memory was extremely expensive, and most machines had 4K or 8K bytes (remember, that means 4,000 or 8,000) at most—and some had a lot less.
Sixteen address lines will address 64K bytes. If you count in binary (which computers always do) and limit yourself to 16 binary columns, you can count from 0 to 65,535. (The colloquial ‘‘64K’’ is shorthand for the number 66,536.) This means that every one of 65,536 separate memory locations can have its own unique address, from 0 up to 65,535."

my questions are how 16 bits address lines can address 64KB?,since 16 bits can only address 64kbps.

and what is segment?

thanks in advance

One address addresses one byte. Using 16 bits, you can write 65536 addresses (from 0 to 65535, that's 65536 different addresses), and address 65536 bytes. 65536 bytes is 64kB. In computer science, b is bit, B is byte. The byte is the smallest amount of memory you can address. The question "what is k ?". k is kilo, in international system of units, a kilo unit is 1000 units, but, when dealing with memory, a kilo unit is 2^10=1024 units, (except when dealing with hard drives, for marketing reasons).

64kbps is 64 kilo bits per second. It is a transfer rate, not an amount of memory.

"What is a segment ?" isn't a precise question, segment is a very generic word used in many contexts. I expect that the 8086 segments are accurate in your context, even if it's some 24-bit addresses with 16-bit CPU instead of 16-bit addresses with 8-bit CPU.


Can any memory-less computer operation be represented in propositional logic? Take any operation that is done by any type of computer (e.g. a cpu on a modern laptop), which doesn't use any type of temporary memory storage.

I.e. this computer operation computes a function $f(x)=y$, without using any form of memory storage.

  Q1: Is it possible for any arbitrary such $f$ to be represented by a formula $\phi(x,y)$ in propositional logic, such that $\phi(x,y) =True$ iff $f(x)=y$?

What if we relax the requirement that no temporary memory can be used?

EDIT: after reading the responses so far, perhaps it makes sense to phrase the question in the opposite way:

  Q1b: What restrictions on $f(x)$ are necessary and sufficient for it to be representable in propositional logic?

Well you can just make a giant truth table for $f$ and then convert that to a Boolean formula. Boolean formulas are propositional formulas, are they not?


invite 12 person from 24 that we have 6 men and 6 womens i had a question and its

"A man has 5 female and 7 male friends and his wife has 7 female and 5 male friends. In how many ways can they invite 6 males and 6 females if husband and wife are to invite 6 friends each?  Answer. 267,148."

i tried to have cases by that each person invited six and total of 6 females and 6 males

1 = 5 mens * 1 female
  +  1 man * 5 females
and cont

and then sum them up but the answer was less than the answer given it was 1848

Say the man invites 2 of his male friends so he has to invite 4 female friends to get to a total of 6. The female fills the gaps - she invites 4 male friends and 2 females. Now the guy has C(5,4) options to invite female friends and C(7,2) for his male friends in this example. The female has C(7,2) for the female part and C(5,4) for the male part.

Now you sum over all variants:


Do the classes $P$ and $NP$ include problems faster then polynomial? I have being reading up on complexity classes (in Rieffel & Polak, 2011; pg149). I am slightly confused about something. Does for example $P$ (DTime($n^k$)) include all problems that can be solved faster then polynomial in time (e.g. logarithmic) on a deterministic Turing? And likewise for e.g. PSpace (DSpace($n^k$)) and NP (NDTime($n^k$)) etc.?

We have $$\mathsf{P} = \bigcup_{k \in \mathbb{N}} DTIME(n^k)$$
And e.g. $\log n \in \mathcal{O}(n)$. Thus, problems which are solvable in deterministic logarithmic time are in $\mathsf{P}$ since they are in $DTIME(n)$.


Converting CFG to CNF need some help with the following question:

I've watched a few youtube tutorials but I'm struggling to convert this specific CFG

What you want is to have each production be of one of the forms $A \rightarrow BC$, $A \rightarrow x$ (for a terminal $x$), and $S \rightarrow \epsilon$ (where $S$ is the start symbol). The only productions in that grammar which are not of one of these forms are:

$\text{S} \rightarrow I \text{ VP PP}$
$\text{VP} \rightarrow ate \text{ NP}$
$\text{VP} \rightarrow \text{V}$

Hints: try replacing the second production with an equivalent one of the form $A \rightarrow BC$, and try replacing the third production with one of the form $A \rightarrow x$. For the first one, I suggest creating a non-terminal $\text{X}$ such that $\text{X} \rightarrow I \text{ VP}$, and then rewriting the production as $\text{S} \rightarrow \text{X} \text{ VP}$. This production is in the correct form, but now the one for $\text{X}$ isn't; however, it isn't too much work to fix that one as well.


How to find specificity of a regex match? I'm thinking about a routing system. Imagine I have the two following regexes

pathpart1/pathpart2 => specific match that routes to controller1
.* => catch-all that routes to controller2

And I let them match on a URL, e.g. 'pathpart1/pathpart2'.

They both match, but I would want to give prevalence to the most specific regex, i.e. the regex where the cardinality of all possible matches of that regex is the lowest.

  Is there a good way to calculate that the first regex has a low cardinality on its match-set (so I want to to go with that match) and the second has a very high cardinality on its match-set (i.e. it is completely not specific, so a match is basically a catch all last resort)...?

I do not know upfront which routes are registered with the router, so I can't loop over them in order of cardinality by hand (i.e. low cardinality first, and the catch-all last if all others don't match).

There are two angles I see to define "specifity" in this context.

Specifity of a regular expression $r$ that matches input $w$ is
the (inverse of the) number of words of length $|w|$ that also match $r$.
Specifity of a regular expression $r$ that matches input $w$ is (the ratio of)
the (maximum) number of symbols of $w$ that are matched by non-wildcard symbols
in $r$ (and $|w|$).

The first option follows your idea: choose among all matches the regular expressions that
matches the fewest others. Since there are in general infinitely many matching
strings, we have to restrict ourselves to a certain length, or a finite set of lengths.

The second option follows another approach. If the input string is well described
by a given expression, long parts of it should be (more or less) explicitly described
in the regular expression. For example, $(aa|ab)+.^*bba$ is a more specific match
for $aaababaababababba$ than $.^*$.

Option 1

In this case, we have to count all words in $\mathcal{L}(r)$ that have length $n$.
Luckily, this is easy once we have an unambiguous, regular grammar¹ $G$ for $\mathcal{L}(r)$.
See here how this can be done.

Option 2

Let's assume we have an unambiguous regular expression (for instance by specifying
lazy wildcards). In that case, we can translate the regular expression into a
DFA. Run the word through it and count how many non-wildcard transitions are taken.

If the expression is ambiguous, we can do the same with the corresponding NFA
if we explore all possible paths.

Convert $r$ to an $NFA$, determinise, convert to right-regular grammar. All
conversions are standard and algorithmically feasible (if not necessarily
efficient).


How to prove this language is not regular (via Fooling Set) By using this fooling set, I am able to prove that the concatenation of bz is in the language L, but I still need to prove that az is not in the language to complete the proof.

This is also the point that the ceiling function is very tricky to deal with. It is also where I am lost.

Any hints and suggestions will be appreciated!

Let $s_1 < s_2 < \cdots$ be a subset of $\mathbb{N}$ with the following property:

$$ \limsup_{n\to\infty} s_{n+1}-s_n = \infty. $$

I will show that the language $L = \{ 0^{s_n} : n \geq 0 \}$ isn't regular using the fooling set method.

The first step is to find indices $i_1 < i_2 < \cdots$ such that
$$
s_{i_1+1}-s_{i_1} < s_{i_2+1}-s_{i_2} < \cdots.
$$
This can easily be done using the given property.

Our fooling set is $\{ 0^{s_{i_n}} : n \geq 0 \}$. To show that this is a fooling set, let $j < k$, and consider the words $x = 0^{s_{i_j}}$ and $y = 0^{s_{i_k}}$. Let $z = 0^{s_{i_j+1}-s_{i_j}}$. Then $xz = 0^{s_{i_j+1}} \in L$ but $yz = 0^{s_{i_k}+s_{i_j+1}-s_{i_j}} \notin L$ since by construction,
$$ s_{i_k} < s_{i_k}+s_{i_j+1}-s_{i_j} < s_{i_k+1}. $$

More generally, a unary language $\{0^s : s \in S\}$ is regular if and only if there exist $N,M$ such that $n \in S$ iff $n+M \in S$ for all $n \geq N$. There are many ways to show it, the most elementary being that a graph of unary DFA consists of a path leading to a cycle. This result implies yours.


Search a preprocessed text with online queries We're given a fixed text, and we are presented with a series of online queries of patterns. For each query, the goal is to answer if the pattern exists in the text. Each pattern is a string, and we want to know if it appears as a substring of the text. The text can be preprocessed.

What's the optimal way to solve this?

By building a suffix trie.

If you wish to preprocess the search query, then there is this algorithm by Boyer–Moore, whose complexity is believed to be linear after applying Galil Rule (details in the same page).

Other than that, if you can preprocess the whole text before hand and construct a Suffix Trie, then you can achieve many things. But the main limitation is it requires a lot of space.

See Suffix Trees and the lecture from MIT (Complete List)

See also Popular String searching algorithms.


Complexity-theoretic difficulty of checking the value of $\pi(x)$? The prime-counting function, demoted $\pi(x)$, is defined as the number of prime numbers less than or equal to $x$.

We can define a decision problem from $\pi(x)$ as follows:

  Given two numbers $x$ and $n$, written in binary, decide if $\pi(x) = n$.

A friend and I were talking about this problem earlier today. There's a pseudopolynomial-time algorithm for this problem - just count up to $x$, using trial division at each step to see how many of the numbers are prime, and check if that's equal to $n$. The problem is also in PSPACE, since the algorithm I just described can be implemented to use only polynomial auxiliary space.

However, I'm having trouble finding a way to place this problem into a lower complexity class. I can't see how to build a polynomial-time verifier for the problem, so I'm not sure whether it's in NP, and I can't think of a way to get it into the polynomial hierarchy at all.

What is the most appropriate complexity class for this problem?

Thanks!

This is very much an open problem. I'll sketch some classes that the problem could "naturally" fit in.

Your definition is somewhat awkward to work with, the problem is hard to fit in to any existing complexity class. The language you've defined is the intersection of the languages $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$. So if for instance $\{(x,n)|\pi(x)\leq n\}$ was in class $K$ then $\{(x,n)|\pi(x)\geq n\}$ would be in $coK$. This makes giving a characterization of the language you've defined hard because one would have to state "the intersection of a language in $K$ with a language in $coK$" to give the tightest bound.

The problem "Compute $\pi(X)$" is a problem in $\#P$, where $\#P\subseteq FPSPACE$ is the class of problems of the form "Compute the number of accepting paths of a nondeterministic, polynomial TM". Clearly we can construct a nondeterministic TM that guesses a number $q \leq x$, and then (with AKS) tests whether $q$ is prime.

A decision variant of $\#P$ is $PP$, which is the class of languages that are of the form: "Given a nondeterministic polynomial TM, do at least half the computation paths accept?". Both $\{(x,n)|\pi(x)\leq n\}$ and $\{(x,n)|\pi(x)\geq n\}$ are probably reducible to a problem in $PP$ (by doing some fudging to the aforementioned TM to balance out the number of accepting paths).