Time Complexity of the below code? here is a nested loop where all the variable are integers.This is another question to the thread. I understood the solution part , but stuck in the time-complexity part.

What is the time complexity of the below code and how?

def divide(dividend, divisor):
    """
    :type dividend: int
    :type divisor: int
    :rtype: int
    """
    #Time-complexity ??
    while dividend>=divisor:
        t=0;k=divisor

        while dividend>=k:
            dividend-=k
            k<<=1
            q+=1<<t
            t+=1

    return q

It is $O(\log^2 \frac{\text{dividend}}{\text{divisor}})$.

The inner loop clearly takes at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ time since initially $k= \text{divisor}$ and it is doubled at every iteration.

The outer loop requires at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ iterations since the inner loop subtracts from $\text{dividend}$ the highest multiple $x = k \cdot \text{divisor}$ such that $k=2^i - 1$ for some integer $i$ and $x \le \text{dividend}$.
This is true because initially $k \le \log ( 1+ \frac{\text{dividend}}{\text{divisor}})$ and the same value of $i$ cannot be selected more than two times in a row since $3 \cdot (2^i - 1) = 3 \cdot 2^i - 3 = 2^{i+1} + (2^i-3) \ge 2^{i+1} - 1$.

This analysis is tight in the following sense:
let $\text{divisor}=1$ and $S_j = \sum_{i=0}^j (2^i - 1)$. Let $\text{dividend}= S_\ell$ for some $\ell \ge 2$ of choice.

Clearly $S_j > 2^j - 1$. Moreover, we can show by induction on $j$ that $S_j < 2^{j+1}-1$.

The base case $j=0$ is trivial: $S_0 = 0 < 2^1 - 1 = 1$.
Suppose now that the claim is true for $j-1$:
We have $S_j = S_{j-1} + (2^j - 1) < 2^j - 1 + (2^j - 1) = 2^{j+1} - 2$.

This means that when divisor is $S_j$, the inner loop will subtract $2^{k}-1$ where $k=j$ (in $k-1$ iterations), and the divisor will become $S_{j-1}$. It follows that $\ell$ iterations of the outer loop are needed to reach $S_0 = 0$.

The overall number of iterations of the inner loop is then:
$$
\sum_{i=1}^\ell (i-1) = \sum_{i=0}^{\ell-1} i = \frac{\ell (\ell-1)}{2} = \Theta(\ell^2).
$$

But $\ell \ge \log S_\ell$, since $S_\ell$ has at least $\ell$ binary digits and hence the above quantity is $\Omega(\log^2 S_\ell) = \Omega(\log^2 \text{dividend}) = \Omega(\log^2 \frac{\text{dividend}}{\text{divisor}})$.


How LL Grammars are subset of DCFL? I have seen in most of the places written that LL grammars form a subset of DCFL and DCFG. Is there a proof for that?

You don't have to prove that LL-grammars form a subset of DCFG. It is just a definition. For example according to the Wikipedia:

  Restricting the DPDA to a single state reduces the class of languages accepted to the LL(1) languages.

This is more about LL-parsers.

LL(1)-grammar alternatively can also be defined as

  A grammar whose parsing table has no multiply-defined entries is said to be LL(1). The first "L" in LL(1) stands for scanning the input from left to right, the second "L" for producing a leftmost derivation, and the "1" for using one input symbol of lookahead at each step to make parsing action decisions.

The latter definition is taken from Aho, Sethi, Ullman's "Compilers" book.

In general $LL(k)$ parser may lookahead $k$ tokens to decide what production rule to apply.

However, you might be given a grammar $G$ and prove that this grammar is, for example, LL(1). In this case you could create a parse table and check if it has no multiply-defined entries.


Simplest complete combinator basis pair for flat expressions In Chris Okasaki's paper "Flattening Combinators: Surviving Without Parentheses" he shows that two combinators are both sufficient and necessary as a basis to encode Turing-complete expressions without the need for an application operator or parentheses.

Compared to John Trump's encodings of combinatory logic in "Binary Lambda Calculus and Combinatory Logic" through prefix coding S and K combinators with an application operator, only needing two combinators for flat expressions increases the code density to optimality. The resulting Goedel numbering maps every integer to a valid, well-formed closed-term expression unlike most calculi and minimal description length relevant esolangs whose canonical representations usually permit descriptions of syntactically invalid programs.

However Okasaki's encoding was meant to be most helpful in a one-way mapping from lambda calculus terms to bitstrings, not necessarily the other way around as the two combinators used in this reduction are relatively complex when used as practical substitution instructions.

What is the simplest complete combinator basis pair that does not require an application operator?

Coming back to this nearly a year later, I realized I had missed some critical research before posting.

Jot seems to fit the bill of what I was asking for, with two relatively simple combinators B & X that can be represented by a compact Goedel numbering.

I've simplified his reference implementation with Python:

def S(x): return lambda y: lambda z: x(z)(y(z))
def K(x): return lambda y: x
def X(x): return x(S)(K)
def B(x): return lambda y: lambda z: x(y(z))
def I(x): return x
def J(n): return (B if n & 1 else X)(J(n >> 1)) if n else I

J(n) returns the built up function denoting the program represented by its Goedel number n.

B (equivalent to Church encoded multiply) serves the function of functional application (parentheses), and can isolate the S/K halves of the single-basis Iota combinator X.

There a few important properties of this language that I'm (almost) shamelessly stealing from the website of the language's inventor Chris Barker, circa 2000.

Jot is a regular language in syntax but Turing-complete. You can see from the implementation of J(n) that if a host language supports tail-recursion, there's no stack space required to parse the bitstring program format.

The proof of Turing-completeness comes from Chris's site as well, implementing the already known Turing-complete combinatory logic using the S and K combinators:

K  ==> 11100
S  ==> 11111000
AB ==> 1[A][B], where A & B are arbitrary CL combinators built up from K & S

Jot has no syntax errors, every program given its Goedel number n is a valid program. This is probably the most important aspect to my own research, as it not only simplifies parsing to triviality, but should also in theory make Jot far more parsimonious than any Turing-complete encoding that has to skip over malformed programs.

I've written a few tools to 'solve' via brute force the semi-decideable problem of finding a function's Kolmogorov complexity in Jot. It works by relying on the programmer to specify some very characteristic training examples of a function's mapping, then enumerates all Jot programs until all training examples are matched, and lastly attempts a proof of equality of a found function with the original verbose implementation.

It currently only works for up to ~40 bits with my limited resources. I'm attempting a rewrite with a SAT solver to learn much larger programs. If you know how to unroll bounded nested closures as a boolean formula, please help out with my new question.

Now for some interesting comparisons to John Tromp's Binary Lambda Calculus, which is known for its conciseness, but does have the problem of possible syntax errors. The following programs were generated by my learning program in a few seconds.

Function    Jot       Binary Lambda Calculus   |J| |B|
--------|----------|--------------------------|---|---
SUCC      J(18400)  "000000011100101111011010" 15  24
CHURCH_0  J(154)    "000010"                    8   6
CHURCH_1  J(0)      "00000111010"               1  11
CHURCH_2  J(588826) "0000011100111010"         20  16
IS_ZERO   J(5)      "00010110000000100000110"   3  23
MUL       J(280)    "0000000111100111010"       9  19
EXP       J(18108)  "00000110110"              15  11
S         J(8)      "00000001011110100111010"   4  23
K         J(4)      "0000110"                   3   7
AND       J(16)     "0000010111010000010"       5  19
OR        J(9050)   "00000101110000011010"     14  20

From my own experiments, the hypothesis that Jot leads to smaller programs is slowly being confirmed as my program learns simple functions, composes them, then learns larger functions from an improved ceiling.


Does the performance of matrix multiplication depend on the storage of the array? Two matrices can be stored in either row major or column major order in contiguous memory. Does the time complexity of computing their multiplication vary depending on the storage scheme? That is, I want to know whether it will work faster if stored in row major or column major order.

The asymptotic complexity will not change with relation to how the matrices are laid out in memory, but the actual running time of the matrix multiplication will be very dependent upon the memory layout.  There are two papers that I know of that go into detail about this, one by McKellar in 1969 and another by Prokop in 1999.  Prokop's paper defines the concept of cache complexity which is related to the number of cache misses the algorithm will incur.

The two papers can be found here:
http://supertech.csail.mit.edu/papers/Prokop99.pdf and here: http://dl.acm.org/citation.cfm?id=362879

The short version is, an $O(n^3)$ algorithm will still be an $O(n^3)$ algorithm (assuming you are using the straightforward matrix-multiply).  However, by taking into account the memory hierarchy of the system, you can significantly speed up that $O(n^3)$ algorithm.


How to prove that these two languages are regular, or not regular? I have these two languages

$L_1={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$

$L_2={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$

As you can see that there is only one difference, the condition of m is different.

My question is to determine whether these two languages are regular or not, and to prove it.

If one or both these languages are non-regular. then how can we prove that using pumping lemma?

These two languages have so many conditions, I am just confused that how to solve these kind of Languages.

Hints:

One of the two languages is not regular. It is the one that forces you
to count beyond 10 to decide whether some strings are in the language.
Regular languages are not very good at counting without bound.

However, the use of the pumping lemma to prove it requires that you start from a
string in the language where $n$ is as close to $m$ as permitted by
the definition of the language, and that you pump out rather than in,
i.e. remove the only $w$ of the $xwy$ decomposition of the string,
rather than inserting more copies of $w$.

Alternatively, you can prove that the reverse of the language is not
regular, if you know about closure properties.


How would one implement a Frequently Used algorithm? The iOS emoji keyboard has a Frequently Used section. Notably, this is different from a Recently Used implementation - the data structure behind it is not an array of emoji where once you use an emoji it is inserted in the array (after first removing it if it already exists). But neither does it appear to be implemented as if it were titled Most Often Used - it doesn't appear to simply be sorting by the symbols you've used the highest number of times. There are more smarts to it. It seems the algorithm is taking into consideration how many times you've used each symbol, but also when it was used, and sorting it on some combination. For example I recently used an emoji just one time and yet it appears in my Frequently Used list towards the end but before other emojis that I know I've used multiple times in the past but haven't used very recently.

If one wished to recreate the iOS Frequently Used algorithm, how would one do so, what exactly does this algorithm do?

You are running into a situation where the task is not "here is a specification of what constitutes a good value, find the best one", but "find a result that is as useful as possible to the user, with no clear specification what 'useful' means".

It's a difficult problem. You can't even ask the users what they think is most useful - because they don't know, and even if they have an opinion what they think is most useful, that doesn't necessarily agree with reality.

You might also consider that changing the set of emojis is of slight negative value because it's harder to find one if the set is changing. On the other hand, emojis that are easy to find anyway (for example smileys that come first in the ordinary list) are less useful. And you might consider context, a user might use different emojis depending who is going to receive the message. Imagine the software knows the receiver, and knows it is their birthday, and suddenly the set of "most useful" emojis totally changes.

I'm not sure if I would count this under "algorithm", because the real problem is not the algorithm, but producing heuristics what makes a good set of useful items.


How can a set of N players be split into M teams, given certain rules? A lot of times, I’ve needed to split a given set of people into a given number of teams but with some complications, like:

Alice and Bob CANNOT be on the same team.
Carol and David just HAVE TO BE on the same team.

I feel like this is already a thing. There's gotta already be work in this problem. Where would I even start, in terms of an algorithm? It definitely can't be brute-forced.

Denote each person as a single vertex and connect them by an edge if they are not allowed to be in the same team. If several people have to be on the same team, use a single vertex to represent all of them. Then color the resulting graph by $k$ colors, where $k$ is the number of teams.This problem is the graph coloring problem. To complicate things you may require color certain vertices in the same color. Please follow this for other types of colorings.


Is this language context free L=${a^mb^nc^pd^q: m+n=p+q}$? L={ $a^mb^nc^pd^q: m+n=p+q$ }

I cannot find a grammar to prove that it is context free.
However I can visualise a PDA which can accept this language.
The PDA would push O's for every a and b which it can later match against c and d.

Please someone suggest a grammar for this language ?

You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{align*}
S & \rightarrow aSd \tag{1} \\
S & \rightarrow T \\
S & \rightarrow V \\
S & \rightarrow U \\
S & \rightarrow \epsilon \\
T & \rightarrow aTc \tag{2} \\
T & \rightarrow V \\
T & \rightarrow \epsilon \\
U & \rightarrow bUd \tag{3} \\
U & \rightarrow V \\
U & \rightarrow \epsilon \\
V & \rightarrow bVc \tag{4} \\
V & \rightarrow \epsilon
\end{align*}
Edit: I've simplified the rules so that fewer terminal symbols appear in it, and adapted the proof.

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminal $U$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminal $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.

A word $w = a^nb^mc^pd^q \in{} L$ can be constructed as follows:

Apply the rule (1) $\min(m, q) =: l$ times. You get $$\underbrace{a\ldots{}a}_{l}S\underbrace{d\ldots{}d}_l$$.
If $m \geq l$ apply rules $S \rightarrow T$ and then (2) $\min(p, m - l) =: k$ times, and you get $$\underbrace{a\ldots{}a}_{l + k }T\underbrace{c\ldots{}c}_k\underbrace{d\ldots{}d}_{l = q}$$ If $k = p$ than $n$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $k = m -l$ and $a$ appears $l + k = m$ times. Apply rule $T \rightarrow V$, rule (4) $p - k$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}_{m}\underbrace{b\ldots{}b}_{p - k}\underbrace{c\ldots{}c}_{k + p - k = p}\underbrace{d\ldots{}d}_{q}$$ Since $m + n = p + q$ proved already above, $p - k = n$ follows and you are finished.
Otherwise $q > l$, and you must apply rule $S \rightarrow U$, and rule (3) $\min(n, q - l) =: g$ times. You will get $$\underbrace{a\ldots{}a}_m\underbrace{b\ldots{}b}_gU\underbrace{d\ldots{}d}_{g + l}$$ If $g = n$ than $p$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $g = q - l$ and $d$ appears $l + g = q$ times. Apply rule $U \rightarrow V$, rule (4) $n - g$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}_{m}\underbrace{b\ldots{}b}_{g + n - g}\underbrace{c\ldots{}c}_{n - g = p}\underbrace{d\ldots{}d}_{q}$$ Since $m + n = p + q$ proved already above, $n - g = p$ follows and you are finished.


() = ( − 2) + 4, giving asymptotic bounds How do I go about solving this? When I try to google examples I only see problems with "+1" or "+n" constants and never anything above that.

If possible could anyone also describe the suggest method to solve these as well?

() = 3( − 1) + 3

() = 2 (/8) + 4^2

Update: I couldn't find any examples or helpful resources for solving recurrences with "weird" constants so I figured it would be unique enough to ask here.

Take the first example. Start calculating T (100) = T (98) + 4 = T (96) + 4 + 4 = T (94) + 12 = T (92) + 16 ...

Seriously, that's the first thing you do. You have a problem, you try what happens. At this point it should be absolutely obvious to you what happens, right? I hope I don't have to write down the solution?

The next one: T (100) = 3 T (99) + 3 = 9 T (98) + 9 + 3 = 9 * T (98) + 12 = 27 * T (97) + 39 = 81 * T (96) + 120 ... Slightly more complicated, but you see that one of the numbers is a power of 3, and the other one is slightly less obvious $(3^k - 3) / 2$. Figure it out from there.

The next one: Well, I'll start with 512. T (512) = $2 T (64) +  4 * 512^2$ $2 * (2 T (8) + 4 * 64^2) + 1024^2$ = $4 T (8) + 8 * 64^2 + 4 * 512^2$ = $4 * (2 T (1) + 4 * 8^2) + 8 * 64^2 + 4 * 512^2$ = $8 T (1) + 8 * 8^2 + 8 * 64^2 + 4 * 512^2$ - it should be clear what the dominating factor is in this equation.

This is all mathematically trivial. All you had to do to solve these problems is to not look at them and be stunned by the strange formulas but having a go and starting to calculate and see what happens.

PS. The answer was intended to demonstrate that seemingly hard problems can often be attacked quite easily, that overcoming your fear of the unknown and jumping in and seeing what happens is often enough. That is much, much more important than solving one particular problem. You may call this a "waste of time", but I Don't Think So.

The quoted "reference answer" may answer the question, but doesn't inspire anyone to try finding the answer themselves.


Why do we simulate the universal TM to simulate another TM M instead of simulating M directly? In the proof of the time hierarchy theorem given on page 69 of Arora-Barak, we define a TM D as follows:

"On input $x$, run for $|x|^{1.4}$ steps the Universal TM $\ \mathcal{U}$ of Theorem 1.9 to simulate the execution of $M_x$ on $x$." Here $M_x$ is the machine encoded by string $x$.

Since we are simulating another TM on $D$, this would implicitly make $D$ a universal TM, right? If this is the case, then why is it necessary to state that $D$ will simulate $\mathcal{U}$ in order to simulate $M_x$ when $D$ is already capable of simulating $M_x$ directly?

On the other hand, if it is not the case that $D$ is a UTM, then why can't we "run" (whatever that means) $M_x$ directly on $x$ instead of running $M_x$ through $\mathcal{U}$ (in the same way that we "run" $\mathcal{U}$)? Why do we need to simulate a machine capable of simulating an arbitrary TM if we only need to simulate exactly one TM?

The difference between $\mathcal{U}$ and $M_x$ is that $\mathcal{U}$ can be hardcoded while $x$ is an input to the machine.

In other words, when Arora and Barak write "run $\mathcal{U}$ to simulate $M_x$", what they mean is to switch to a part of the Turing machine which behaves like $\mathcal{U}$ (you can think of it as a function), and afterwards switch to some other part of the machine. The states of $\mathcal{U}$ do the work of simulating $M_x$.

You are not simulating $\mathcal{U}$. You incorporate its code as part of your Turing machine. (In programming languages, this is sometimes known as inlining.)


Searching for a string of numbers in a large digit sequence How would one search for a string of digits in a large digit sequence? For example, I'd like to search for 351814 in Euler's number. I'm not too keen on computer science, I'm a pure math major, so I don't really know how to begin. I also wouldn't know how to run said code.

Any help would be greatly appreciated.

Use your web browser. You can get the first 2 million or so digits in this link, and then use your browser's searching facilities. I was able to locate 351814 within the first 2 million digits (though not within the first 1 million digits, available in a separate link). By the way, I found both links on Wikipedia.


Randomized Algorithms: High-Probability vs. Expectation Hopefully this question isn't too general, but I was wondering what the relationship is between randomized algorithms that perform well with high-probability and those that perform well in expectation. My question is motivated by the definition of a randomized $\alpha$-approximation algorithm given here, namely that it is a polynomial-time algorithm that produces a solution within $\alpha$ of OPT in expectation or with high probability. I also found that the first few pages of this source provides some good insight into the high-probability vs. expectation approaches, but I still have questions.

Can you always transform an algorithm that achieves an $\alpha$-approximation in expectation to one that achieves this with high probability, and vice versa? (Ostensibly by rerunning the algorithm multiple [a polynomial number] of times.)
If not, is one harder than the other to obtain? (I would think that if you fix $\alpha$, a high-probability algorithm would always be harder to find/less likely to exist. Or maybe you can always find one, but the approximation ratio will become worse.)

Thanks for the help!

If you have an algorithm that is an $\alpha$-approximation in expectation, then you can construct an algorithm that is a $(1+\epsilon)\alpha$-approximation with high probability, for any $\epsilon>0$.  In particular, by Markov's inequality, if you run the algorithm, then with probability at least $1-1/(1+\epsilon)$ it will output a $(1+\epsilon)\alpha$-approximation.  So, if you run the algorithm about $(c \log n)/\epsilon$ times and keep the best output among all of those trials, with probability about $1-1/n^c$ you will find a $(1+\epsilon)\alpha$-approximation.
If you have an algorithm that is an $\alpha$-approximation with high probability, there are no guarantees about the expectation.  It's possible that with very small probability (probability $1/n^c$), it outputs an extremely bad solution (one with exponentially large approximation factor), and in all other cases it outputs an $\alpha$-approximation.  In this case, the expected value of the approximation factor will be very large, even though it has a very small probability to output such a bad solution.


How to sort a large list of elements where everything is sorted but k elements? Assuming the list is very large, and $k$ is very small, what's the fastest algorithm to sort this list?

Here is an $O(k \log k + n)$ Algorithm. Assuming we are dealing with an ascending order. We assume $A$ is a linked list, an hence removing elements can be done in constant time. Given an array instead, we can preprocess it in linear time building a linked-list out of it.

Let A be a given list of n elements.
Let B be an empty array.
For x in A do
- Let y be the element following x.
- As long as y < x then
- - Add x to B.
- - Add y to B.
- - Remove x from A.
- - Remove y from A.
- - If x was the first element,
- - - then break from the inner loop.
- - Set x to the previous element of x.
- - Set y to the following element of y.
Sort B with any efficient sorting algorithm.
Unify A and B in the array C efficiently.
Return the array C.

If an element $x$ is greater than the following element $y$, then at least on of them must be one of the $k$ elements, because else they must be sorted. Hence, we do not remove more than $2k$ elements from $A$. Since with each visit of the inner-loop except for the last one, we remove two elements from the array, and since we do not remove in total more than $2k$ elements, the total number of visits of the inner loop is at most $2k+n$. The size of $B$ is at most $2k$, since it only has the elements removed from $A$. Using quick-sort, we can sort $B$ in running time $O(k \log k)$ (note that $B$ is an array and not a list). Unifying two sorted arrays/lists in a new sorted list can be achieved in linear time using sliding-window.
The total running time is $O(n + 2k + k \log k + n + k) = O(k \log k + n)$.


Why are ADT packages opened immediately after they are built, while existential objects opened as late as possible? Section 24.2  in Types and Programming Languages by Pierce defines ADTs in existential types:

  A conventional abstract data type (or ADT) consists of (1) a type name A, (2) a concrete representation type T, (3) implementations of
  some operations for creating, querying, and manipulating values of
  type T, and (4) an abstraction boundary enclosing the representation
  and operations. Inside this boundary, elements of the type are viewed
  concretely (with type T). Outside, they are viewed abstractly, with
  type A. Values of type A may be passed around, stored in data
  structures, etc., but not directly examined or changed—the only
  operations allowed on A are those provided by the ADT. ... We ﬁrst
  create an existential package containing the internals of the ADT:

counterADT =
{*Nat,
{new = 1,
get = λi:Nat. i,
inc = λi:Nat. succ(i)}}
as {∃Counter,
{new: Counter,
get: Counter→Nat,
inc: Counter→Counter}};

> counterADT : {∃Counter,
{new:Counter,get:Counter→Nat,inc:Counter→Counter}}

  We can open it for example

let {Counter,counter} = counterADT in
counter.get (counter.inc counter.new);
> 2 : Nat

and then defines existential objects  in existential types:

  A counter object comprises two basic components: a number (its internal state), and a pair of methods, get and inc, that can be used
  to manipulate the state. We also need to ensure that the only way that
  the state can be queried or updated is by using one of these two
  methods. This can be accomplished by wrapping the state and methods in
  an existential package, abstracting the type of the state. For
  example, a counter object holding the value 5 might be written

c = {*Nat,
{state = 5,
methods = {get = λx:Nat. x,
inc = λx:Nat. succ(x)}}}
as Counter;

  where:

Counter = {∃X, {state:X, methods: {get:X→Nat, inc:X→X}}};

  We opens it for example:

let {X,body} = c in body.methods.get(body.state);
> 5 : Nat

and  compare ADTs and existential objects:

  when programming with ADTs, packages are opened immediately after they are built; on the other hand, when packages are used to model
  objects they are kept closed as long as possible—until the moment
  when they must be opened so that one of the methods can be applied to
  the internal state.

What does "when programming with ADTs, packages are opened immediately after they are built; on the other hand, when packages are used to model objects they are kept closed as long as possible" mean?

They are both opened in the binding parts of the let terms, which can be anywhere (not immediately) after they are built. So their timings seem to be the same to me.
What are the differences in the definitions of ADT and of existential objects in terms of existential types, which lead to the timing difference of their opening?

Thanks.

You can see an instance of the claimed property in the two definitions of add3.

In the ADT style, add3 is defined as:

let { Counter, counter } = counterADT in
let add3 = λ (c : Counter). counter.inc (counter.inc (counter.inc c)) in
counter.get (add3 counter.new);

As you see, in order to call about inc, one must already have opened the existential package. You cannot write the inc3 function in the "ambient scope", as Counter is not an ambient type, but a type encapsulated in the counterADT package.

You could repackage everything after the first call to inc, and re-open the package before the next call, but that would be somewhat pointless.

In the object style, add3 is defined as:

add3 = λ (c : Counter). sendinc (sendinc (sendinc c)))

Here, the client code does not open the existential package themselves.  Instead, each call to sendinc will open the package when it needs to run inc, and will repackage the output.  The client could just do the same, but that is not the intent of this style (they would be breaking the abstraction).

So, the confusion might be that you understood the sentence as "the packages are open at a given time", as opposed to "a programmer would be expected to open the package at a given time".

The difference in timing comes from the way we want to use these two mechanisms.

The ADT mechanism is one where we have a single representation, that we wish to hide, while giving some actions to perform on that representation.  Because there is a single representation, it is perfectly acceptable to unpackage it once and for all.

The object mechanism is one where we want to potentially allow multiple representations that all share some actions to perform on them.  Because we want to allow multiple representations, each package should be responsible for knowing how to perform the abstract action on its concrete representation.  If we were to unpackage the existential type early, we would locally be restricted to a given representation.

This becomes very interesting when thinking about binary operations over the packaged type: in the ADT style, the two operands are guaranteed to share the same representation, whereas in the object style, each operand could have its own concrete representation and its own way of implementing the binary operation.

http://www.cs.utexas.edu/~wcook/Drafts/2009/essay.pdf

^ This paper, "On Understanding Data Abstraction, Revisited", by William R. Cook gives a lengthy explanation of the difference in power between these two approaches, and is, in my opinion, an excellent read.


Asymptotic growth of search algorithms I have 2 search algorithms and I have derived the following tight bound representations:

$$ nlog(n)+mlog(n) $$

$$ m∗n $$

Now i want to find a function $f(n)$ so that when $m$ is an element of tight bound $f(n)$, both algorithms have equal asymptotic run time.

Now I'm not sure if its just as simple as setting the two equations equal to each other and isolating 'm' or of it is more than tha

Your approach, for this problem at least, will work, but there are interesting things happening in the background. Simply setting the two terms equal and solving for $m$ will give you
$$
m=\frac{n\log n}{n-\log n}
$$
However, I doubt that you want to substitute this back into the two original expressions and try to find a $g(n)$ so that each of your original expressions is in $O(g(n))$. Let's try something else.

For no particular reason, let's try letting $m=\log n$. Then your two expressions become
$$\begin{align}
n\log n+m\log n&=n\log n+\log^2n \in O(n\log n)\text{, and}\\
n\:m&=n\log n\in O(n\log n)
\end{align}$$
Hooray! If $m=f(n)=\log n$ we get a common upper bound with $g(n)=n\log n$.

Let's do the same thing, now with $m=n$. The two expressions are now
$$\begin{align}
n\log n+m\log n&=n\log n+n\log n \in O(n\log n)\text{, and}\\
n\:m&=n\; n\in O(n^2)
\end{align}$$
Drat. No common upper bound, but by transitivity, we have $n\log n+m\log n\in O(n^2)$ and so again, we find a common upper bound, namely the asymptoticly larger $g(n)=n^2$.

You can do this for all kinds of other $f(n)$, like $f(n)=\log\log n$ and even $f(n)=1$, both of which have common solutions $g(n)=n\log n$. In fact, it seems that we can do this for any $f$ whatsoever.


Is concurrent language CCS or CSP turing-equivalent in language power? Does the concurrent language CSP (or CCS, $pi$-calculus) model interacting machines?
Is CSP (or CCS, $pi$-calculus) Turing-equivalent to other programming languages like C?

The answer to your (1) depends on what exactly you mean by "model" and by "interacting machines". The $\pi$-calculus in particular is usually deemed to be a good simplification of  the core aspects of message passing concurrency.

Regarding (2), you can simulate Turing machines in CSP, CCS, the $\pi$-calculus as well as in C. Hence they are all equivalent in terms of the functions they can compute on the natural numbers.


Prove that $L^{\nsubseteq}_{M'}=\{ \langle M \rangle \ | \ L(M) \nsubseteq L(M')\}$ with $M'$ a TM that always halt is undecidable I've done some other problems by reduction, but I'm quite stuck here. I'm not really sure what to do with $M'$. I know that because $L(M) \nsubseteq L(M')$ there exists $w \in L(M)$ and $w \notin L(M')$ and I'm trying to create the  machine that ignores the input and accepts only when M accepts $w$, but I'm kinda stuck on what to do next. Any suggestions?

Don't be confused by this question. Instead of studying $L^{\nsubseteq}_{M'}=\{ \langle M \rangle \ | \ L(M) \nsubseteq L(M')\}$ you might consider as well the language $L_G=\{ \langle M \rangle \ | \ L(M) \nsubseteq G\}$ for $G$ being any language. It is important to notice that there is always a Turing machines $M$ with $\langle M \rangle \in L_G$ but always a machine $M'$ with  $\langle M' \rangle \not \in L_G$. So you are looking for a nontrivial set of Turing machines. This allows you to apply Rice's theorem and you are done.

If you want to get a proof via reduction just look in the proof of Rice's theorem. It shows you how to get a generic reduction for these cases.


Link-cut trees: how to code cut(u,v) In most bibliography, only cut(v) is defined.
More properly, only cut(v,v.parent) is defined, where (v,v.parent) is an edge in the represented tree.

The pseudo-code and code for this is:

cut(x):
   access(x);
   parent(left(x)) = null
   left(x) = null

void cut(Node *x){
   access(x);
   x->left->parent = 0;
   x->left = 0;
}

  How can we define cut(u,v) for an arbitrary (u,v)?

  I.e. how can we code cut(u,v) in such a way that

  If (u,v) is not an edge in the represented tree, then do nothing;
  If (u,v) is an edge of the represented tree, cut the edge in the represented tree.

The following function may help, it determines the root of the represented tree that contains the node x.

root(x):
   access(x)
   while(left(x) =/= null)
      x = left(x)
   splay(x)

LCT *root(LCT *x){
   access(x);
   while((*x).left != NULL){
       x = (*x).left;
   }
   splay(x);
   return x;
}

Additional reference (code): https://github.com/saadtaame/link-cut-tree

Thanks in advance.

The function $cut(v)$ is only defined for cutting $v$ from its parent for a reason, because this is the only possibility. The represented tree is first and foremost a Tree. By definition, edges will only exist from a parent to a child. Therefore, the only edge you would ever need to cut is from parent to child.


Comparing two graphs I want to compare the vertices of two graphs. Given two graphs, $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$, I want to compare $u_n$ and $v_m$ for $u \in V_1$ and $v \in V_2$. I came up with double loops for doing this:

for all u in G1
  for all v in G2
    if u.label == v.label then
       do something here
    end if
  end for
end for

Now the above two loops have the time complexity of $O(n) = n^2$. Is there a better way of doing this , i.e. a more efficient algorithm, assuming that no other information is available?

I looked at the raph isomorphism problem (https://en.wikipedia.org/wiki/Graph_isomorphism_problem). But here I am not trying to find out if the two graphs are isomorphic.

Is there a better/more efficient approach for doing this?

A more efficient approach would be to group the vertices according to their labels, and only run the double loop for vertices in the same group. In the worst case (if all vertices have the same label) this is still $\Omega(n^2)$, but if there are relatively few vertices sharing the same label this is much more efficient.

This also assumes that the "do something"-bit doesn't change the label (and that the order of the "do something"s doesn't matter).


Context free grammar issue at pda I'm studying for my computing languages and I have some problem on getting the production rules from a push down automata.

The automaton accepts all strings over alphabet $\{e,k,q,y\}$ of the form $w\,kyyk\,w'$ such that $|w|=|w'|$.

There are the productions rules I get.

S -> QkyykK
Q -> qQ
Q -> yQ
Q -> eQ
Q -> kQ
Q -> epsilon

K -> Kq
K -> Ky
K -> Ke
K -> Kk
K -> epsilon

I don't understand how to have the same number on the left and on the right. Hope anyone can help me or explain me cause I am having so problems with that exercice. I use jflap for testing if it's accepted or rejected.

You enforce the property of having an equal number of characters to the left and the right by only having rules that add an equal number of characters.

At the moment, your approach is essentially, "Start with $kyyk$ and add stuff to the left and the right." In this  case, "stuff" is the non-terminal symbols $K$ and $Q$, each of which can expand to any string in $\Sigma^*$. Whenever you're expanding two non-terminals in a context-free language, they're expanded completely independently, so there's no way to control their interaction, e.g., to require that both strings have the same length.  This means that the approach of generating the left-stuff and right-stuff from two  non-terminal symbols can't work.

Instead, you need to take the opposite approach. Start with nothing and simultaneously expand the stuff on the left and right.


Solving or approximating recurrence relations for sequences of numbers In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested mainly in the sequence's asymptotic growth.

Examples are

The runtime of a tail-recursive function stepping downwards to $0$ from $n$ whose body takes time $f(n)$:

$\qquad \begin{align}
  T(0) &= 0 \\
  T(n+1) &= T(n) + f(n)
 \end{align}$
The Fibonacci sequence:

$\qquad \begin{align}
  F_0 &= 0 \\
  F_1 &= 1 \\
  F_{n+2} &= F_n + F_{n+1}
 \end{align}$
The number of Dyck words with $n$ parenthesis pairs:

$\qquad\begin{align}
    C_0 &= 1 \\
    C_{n+1}&=\sum_{i=0}^{n}C_i\,C_{n-i}
  \end{align}$
The mergesort runtime recurrence on lists of length $n$:

$\qquad \begin{align}
  T(1) &= T(0) = 0 \\
  T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1
 \end{align}$

What are methods to solve recurrence relations? We are looking for

general methods and
methods for a significant subclass

as well as

methods that yield precise solutions and
methods that provide (bounds on) asymptotic growth.

This is supposed to become a reference question. Please post one answer per method and provide a general description as well as an illustrative example.

Converting Full History to Limited History

This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers.  Consider, for example, the recurrence
$$
T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)
$$
which arises in the analysis of randomized quicksort.  (Here, $k$ is the rank of the randomly chosen pivot.)  For any integer $n$, the value of $T(n)$ depends on all $T(k)$ with $k<n$.  Recurrences of this form are called full history recurrences.

To solve this recurrence, we can transform it into a limited history recurrence, where $T(n)$ depends on only a constant number of previous values.  But first, it helps to simplify the recurrence a bit, to collect common terms and eliminate pesky fractions.
\begin{align*}
n T(n) &= n^2 + 2\sum_{k=1}^{n-1} T(k)
\end{align*}
Now to convert to a limited-history recurrence, we write down the recurrence for $T(n-1)$, subtract, and regather terms:
\begin{align*}
(n-1) T(n-1) &= (n-1)^2 + 2\sum_{k=1}^{n-2} T(k)
\\
\implies
nT(n) - (n-1)T(n-1) &= (2n-1) + 2T(n-1)
\\[1ex]
\implies
n T(n) &= (2n-1) + (n+1) T(n-1)
\\[1ex]
\implies
\frac{T(n)}{n+1} &= \frac{2n-1}{n(n+1)} + \frac{T(n-1)}{n}
\end{align*}

Now if we define $t(n) = T(n)/(n+1)$ and replace the fraction $\frac{2n-1}{n(n+1)}$ with the simpler asymptotic form $\Theta(1/n)$, we obtain the much simpler recurrence
$$
t(n) = \Theta(1/n) + t(n-1).
$$
Expanding this recurrence into a summation immediately gives us $t(n) = \Theta(H_n) = \Theta(\log n)$, where $H_n$ is the $n$th harmonic number.  We conclude that $\boldsymbol{T(n) = \Theta(n\log n)}$.


"Practical forms" of Chernoff bound for inequality in expectation From Wikipedia:

The above formula is often unwieldy in practice, so the following looser but more convenient bounds are often used:
(i) $Pr(X\geq (1+\delta)\mu)\leq e^{-\frac{\delta^2\mu}{3}}, 0<\delta<1$
(ii) $Pr(X\leq (1-\delta)\mu)\leq e^{-\frac{\delta^2\mu}{2}}, 0<\delta<1$

The assumption they use is $E[X]=\mu$.
Would (i) still hold if we only assume $E[X]\leq \mu$? Would (ii) still hold if we only assume $E[X]\geq\mu$?
If not, what "practical forms" do we have in these cases?

It is more practical just because it has

  the advantage of being easier to state and compute with in many situations (quoted from [1]).

I am not sure whether (i) still holds for $\mu' = E[X] \le \mu$. At least, we cannot obtain that directly from the following computation:

$$Pr[X \ge (1 + \delta) \mu] \le Pr[X \ge (1 + \delta) \mu'] \le e^{-\frac{\delta^2 \mu'}{3}} \ge e^{-\frac{\delta^2 \mu}{3}}$$

[1] Mitzenmacher, Michael and Upfal, Eli (2005). Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. ISBN 0-521-83540-2.


Can GDB debug itself? Can GDB be run on itself? How or why not?
I see something about it http://www.math.utah.edu/docs/info/gdbint_3.html
But GDB might not be written in a language that it can debug?

Yes, it's possible. Here's how to do it.

Obtain the source code for gdb.
Compile with the -g flag on.
Run gdb gdb.


(OCR ) How to Recognise Handwritten fractional numbers using Neural networks I want to be able to recognise handwritten math numbers using images of the numbers , i was able to do  create a ANN model for recognising simple decimal numbers , but i have no idea on how to recognise fractional number.
What kind of ML model do i need to recognise fractional numbers (p/q forms). As i am relatively new to machine learning, i have no idea how to do it. Any study material will be appreciated.

Usually one of the steps is "segmentation", where we separate the image into smaller images, one for each character/symbol.  Thus the fraction "1/13" would have four character, "1", "/", "1", and "3".  Then, you apply a neural network separately to each of those four smaller images.

See https://en.wikipedia.org/wiki/Optical_character_recognition for an introduction.  OCR is covered in many standard sources.  I suggest reading the literature on the subject to learn more about standard methods.


Differences between the OS and DB buffer pool? How does the DB manage a pool of buffers when the operating system ends up controlling what's really in memory? For example, couldn't the operating system decide to evict a page frame from a DB's buffer?

Yes, absolutely, that could happen, and it makes it harder for databases to optimize their own performance.

Some databases bypass the operating system's virtual memory management and manage memory themselves.  They might request that the operating system pin a range of the address space into memory (and never page it out).  Or, they might be designed to be the only application that runs on the machine, and take care of their own memory management so they never use too much memory -- hoping that this will make it unlikely that the OS ever pages out any of their data.


Reduction from a m-coloring to a m-partition define a m-partition as: Given an undirected graph G = (V, E) and an integer j. Does there exist a partition of the vertices into m parts {V1, V2, ... , Vm} such that at least j of the edges have their endpoints in different parts of the partition?

I started by partitioning the graph into k parts: each partition represents 1 colouring of the graph. From there, I thought of reverting all edges: so converting all edges into non-edges and vice-versa. I'm stuck here. Am i on the right track? Thank you.

By definition, a $m$-coloring is a function $f : V \to \{1,\dots, m\}$ such that $\forall u,v \in V \; f(u) = f(v) \implies (u,v) \not\in E$. This means that at least $|E|$ edges have their endpoints in different sets of the partition $\{V_1, \dots, V_m\}$ of $V$ with $V_i = \{ v \in V : f(v)=i \}$.

On the contrary, if there is a partition $\{V_1, \dots, V_m\}$ of $V$ such that at least $|E|$ edges have their endpoints in different sets, then the function $f : V \to \{1, \dots, k\}$, where $f(u)$ is the unique index $i_u \in \{1, \dots, m\}$ such that $u \in A_{i_u}$, satisfies $\forall u,v \in V \; f(u) = f(v) \implies (u,v) \not\in E$.

The above shows that the instance $G=(V,E)$ of $m$-coloring can be reduced (w.r.t. Karp reductions) to the instance $\langle G, |E| \rangle$ of $m$-partition.


Why is $\{1^n \mid n > 1\}$ regular? Given the definition of a regular language is one that can be expressed with finite memory, how is $\{1^n \mid n \geq 1\}$  regular? The $n$ is unbounded. I know a DFA can be drawn, which means the language is regular. But I thought another condition is that $n$ must be bounded, so it's as if the 2 tests contradict each other?

If I understand you correctly, the following comment seems to get to the heart of what you're really asking:

  A regular language is one where you can make an automata for it, or a regular expression for it. But this seems like a poor definition to me because how do you know if none exist or you just haven't been able to think it up yet?

That's a fair question.  I'm afraid the answer is -- the definition is what it is.  Whether you consider it poor or not, this is the standard definition of a regular language.  For now, I recommend that you simply accept it and work within it.  I agree that the implications are a bit.. uncomfortable.  Unfortunately, that's life.

Many definitions are like this.  For instance, consider the definition of what it means for a number to be prime: a number $n$ is prime if there it does not have any divisor $d$ such that $1<d<n$.  Of course you can ask: how do you know if such a divisor exists?  Maybe you just haven't been able to find one yet?  The answer is that you might not know... but that's still the definition, and there are good reasons to use this definition, rather than some other.

Ultimately, there are reasons why the standard definition of regular languages is useful.  Those reasons might not be obvious when you are first starting to study the material.  From a computer scientist's perspective, one reason why the notion of a regular language is useful is that it corresponds to what can be accepted by an automaton with finite state, and this has many applications through computer science (parsing by compilers, model checking, and more).  From a mathematician's perspective, the notion of a regular language is interesting because it has many useful properties.

But for now... accept that the definition is what it is, and there are reasons for it to be that way, and go with it.


Solve the recurrence $f(n+1)=f(n)^2,\, f(0)=2$ I have a problem with an exercise asking me to solve the following recurrence:
$$f(n+1)=f(n)^2, \quad f(0)=2$$
Can someone explain how to solve this? I tried but couldn't.

Hint, Consider the function $g(n) = \log_2 f(n)$


Prove that a language is regular if it is accepted by a DFA with more than one intial state So I'm currently studying theory of computation, and I was wondering if you could theoretically have more than one initial state in a DFA and if you can prove that a DFA with more than one initial state can depict a regular language? So essentially, can we prove that a language is regular if and only if it is accepted by a DFA with more than one initial state?

I was experimenting with the language L which consists of all strings over the alphabet {a,b} which contains an even number of a's.

I managed to draw a DFA for this language as well as my representation for a DFA with more than one initial state. From the looks of things, it makes sense.

But is there any way that we can PROVE that a language is regular if it is accepted by a DFA with more than one state? So for any given DFA with more than one initial state, are the languages that it accepts is regular? If so, how can I prove it? I know from Kleene's Theorem that a regular language is accepted by an FA, but from the research I have done I have not been able to find anything regarding my question.

There are many ways of showing that DFAs with multiple initial states generate regular languages. Here are some:

You can prove using Nerode's theorem that for any DFA, the set of words taking the DFA from state $q_1$ to state $q_2$ is regular.
Using "dynamic programming", you can construct a regular expression for the set of all words taking a DFA from state $q_1$ to state $q_2$.
Using $\epsilon$ transitions from a new initial state, you can construct an NFA equivalent to your DFA.

NFAs with multiple initial states are in some sense more natural than NFAs with one initial state. Indeed, the power set construction, which constructs a DFA equivalent to a given NFA, works without any changes for this more general class of NFAs. Moreover, this more liberal definition allows you to prove that regular languages are closed under reversal by simply "reversing all arrows".


What is the reason that is FFT multiplication slower than other methods for small N? I've seen plenty of statements in papers and on websites that Fast Fourier Transform-based multiplication algorithms are slower than other multiplication algorithms for relatively small input size N, and I've seen plenty of data in papers and on websites demonstrating that this is the case, but nothing I've come across has bothered to explain what causes FFT to be slower for small N.

I would guess that the overhead is due to getting the input into a form that FFT can swallow, but I'd like to know what the actual cause of the overhead is and whether it can be reduced.  Note that I'm not talking about switching from some FFT implementation to another method when N is below a certain size as many implementations do, but the source of overhead in the FFT itself and what can be done to reduce it.

The Wikipedia FFT article says that the split-radix FFT algorithm requires $4N\log_2N-6N+8$ real multiplications and additions.  Multiplying 2 degree $M$ polynomials results in a polynomial of degree $2M$, so the "FFT multiplication of two polynomials" goes like this:

FFT (size 2M) of polynomial f(x) (evaluate f(x) at the 2M primitive roots of unity)
FFT (size 2M) of polynomial g(x) (evaluate g(x) at the 2M primitive roots of unity)
multiply each of the 2M fourier coefficients together
inverse FFT (size 2M) of the fourier coefficients to get the resulting polynomial

Perhaps there is a way to make the first two FFTs faster based on the fact that the $M+1$th through $2M$th coefficients of f(x) and g(x) are all zeros, but I don't know it offhand.

So we are doing 3 FFTs of size $2M$ plus an additional $2M$ complex multiplies (each of which is 4 real multiplies and 2 real additions so:
$$3 (4(2M)\lg2M - 6(2M)+8)+4M = 24M\lg M -8M+24$$
additions and $24M\lg M - 4M + 24$ multiplications.

Meanwhile the naive polynomial multiplication algorithm (convolution) takes $M^2$ real multiplications and $(M-1)^2$ real additions.  (Proof left as exercise for the reader.)

Thus the naive algorithm will be faster for $M \leq 128$, while the FFT based algorithm will probably be faster at $M \geq 256$, and the crossover will be somewhere between 128 and 256.  (Proof left as exercise for the reader.)

I did this quickly and sloppily, so I'm probably off somewhere (e.g., the forward FFTs are real -> complex, (but is there a DCT version that would be cheaper?) while the reverse is complex -> real (which may have slightly different constants than the ones I used,) and I only did the evaluation at $M$ power of 2 (FFT of non-power of 2s is more expensive.))  Nonetheless, the point stands: the constant multiplier for the FFT is approximately 24, while the constant multiplier for the naive convolution is 1, so you need to compare (something like) $24M\lg M$ to $M^2$.


Normal form of relation R It is given that for a relation R all the attributes of the relation appear in some of the candidate keys. It is also given that there is only one compound candidate key which exists for a relation, all the other candidate keys are simple candidate keys. What can be said about the normal form of R?

In my opinion, since all the attributes are part of some candidate attribute, it is surely in 3NF. But I am not sure if we can extend our reasoning to claim that R in also in BCNF(as claimed by the solution).

Can anyone please help me out why R can be said to be in BCNF normal form?

Thanks in advance!

If you bring the functional dependencies of R in a canonical form, you can have only dependencies in which the right part is constituted only by a single attribute, which is prime, so we are sure that the relation is in 3NF. More, we can divide those dependencies into three sets:

The dependencies where the LHS is a single attribute candidate key;
Those where the LHS is the (only) compound candidate key;
Those where the LHS is a strict subset of the compound candidate key.

The first two kinds of dependencies are compatible with the BCNF, while the third one is not.

It is easy to show that the last set is empty. In fact, if there were a dependency X -> A, with X a strict subset of the compound candidate key, since A is a candidate key, that is determines all the other attributes, then also X determines all the other attributes, and so it is a candidate key. But this is a contradiction with the hypothesis, so no dependency X -> A where is X is not a superkey can exists, and the BCNF is surely satisfied.


Usual distances on DFAs (Deterministic Finite Automata)? I've been searching in the literature for examples of distances defined on the set of the DFAs (or on the set of minimal DFAs) that are defined on a given alphabet sigma.

Since the languages they describe (regular languages) can potentially have an infinite size, defining a distance is not a trivial matter.

Nevertheless, having a distance on these objects can be useful, in order to fit these in metric spaces, which allows for a range of things (in my case to assess the performance of an algorithm).

My only consistent idea so far is to create a distance similar to the edit-distance in labeled graphs on the minimized DFAs.

Does someone have ever heard of other distances ?

There are many possible distance metrics, and without any criteria, we have no basis to choose.  Here are two plausible ones.

Let $L_1,L_2$ be the languages of the two DFAs.  Let $L$ be the symmetric difference of those languages (i.e., $(L_1 \setminus L_2) \cup (L_2 \setminus L_1)$).

One dissimilarity measure is $d(L_1,L_2) = 2^{-n}$ where $n=\min\{|x| : x \in L\}$, i.e., $n$ is the length of the shortest word in $L$.  This is not a distance metric, because it does not satisfy the triangle inequality.

Another possibility is to use the density of $L$, i.e.,

$$d(L_1,L_2) = \sum_{n=0}^\infty {|L \cap \Sigma^n| \over 2^n |\Sigma|^n}.$$

This one is a distance metric.

These can be computed given DFAs for $L_1,L_2$.  You can easily compute a DFA for $L$.  Then, it is easy to find the length of the shortest word in $L$ using breadth-first search.

Computing the density is a bit trickier, but can be done efficiently using a little more math.  Let $A$ denote the transition matrix of the DFA for $L$, i.e., $A_{ij}=1$ if there is a transition (on any input symbol) from state $i$ to state $j$, or $A_{ij}=0$ if not.  Let $s$ denote the one-hot vector indicating the start state, i.e., $s_i=1$ iff $i$ is the start state, and $f$ denote the one-hot vector indicating the final states, i.e., $f_i=1$ iff $i$ is an accepting state.  Now $|L \cap \Sigma^n| = s^\top A^n f$, so the distance is given by

$$d(L_1,L_2) = \sum_{n=0}^\infty {s^\top A^n f \over 2^n |\Sigma|^n}
= s^\top C f$$

where

$$C = \sum_{n=0}^\infty B^n = {1 \over I - B} = (I - B)^{-1}$$

where $B={1 \over 2|\Sigma} A$ and $I$ represents the identity matrix.  This can be computed in time proportional to the cube of the number of states in the DFA for $L$ using standard algorithms for matrix inversion.


Optimal dividing of K people into N groups A teacher at a school has to do this on a regular basis. Let's say 12 students should be divided into either 4 groups of 3, or 3 groups og 4.
Each student can pick up to 3 other students that person would most rather be with.

I tried to set this up as an undirected weighted graph, and implement shortest path algorithms, but the shortest path here doesn't ensure that as many students as possible get their top wish.

What algorithm should I look into here, in order to achieve to most optimal solution to a problem like this?

Here is a visualisation of the problem:

Solution in pseudocode:

initialize collection of persons (e.g. an array):
    - each person itself is described by its position in collection
    - each person itself contains collection of positions (e.g. an array)
      that describe wished persons for the person to be grouped with
(example: persons = [[1,2], [0,2], [0,3], [0,2]])

initialize empty collection of groups (e.g. an array):
    - each group itself is described by its position in collection
    - each group itself contains collection of positions (e.g. an array)
      that describe grouped persons

initialize number of persons per group (example: 2)
initialize total group count to be number of persons divided by number of persons per group (example: 2)
initialize constraint c1 as: any group shouldn't exceed the number of persons per group
initialize constraint c2 as: group count shouldn't exceed the number of total group count
initialize constraint c3 as minimum required of wishes granted per person in any group, for the solution to be valid (example: 1)
[*]initialize dictionary of solutions, where key is a pair (persons, groups), and value is a solution or an empty value

call group(persons, groups)

procedure group(persons, groups):
    [*]if there is a pair (persons, groups) in dictionary of solutions
    [*] return that solution

    for each person (let's call it this-person)
        for each person among this-persons wishes (let's call it wished-person)
            if wished-person is already grouped in any of the groups
                if this-person can be grouped in the same group with wished-person, at the same time satisfying c1
                    set new-groups as groups with this-person grouped accordingly
                    set new-persons as persons without this-person
                else
                    nothing can be done with wished-person, so continue with the next wished-person
            else
                if both this-person and wished-person can be grouped in any group, at the same time satisfying c1 and c2
                    set new-groups as groups with this-person and wished-person grouped accordingly
                    set new-persons as persons without both this-person and wished-person
                else
                    nothing can be done with wished-person, so continue with the next wished-person

            if there are any other persons left in new-persons
                set possible-solution to recursive call, group(new-persons, new-groups)
                if possible-solution is not empty
                    [*]add item to dictionary of solutions, key is the pair (persons, groups), value is possible-solution
                    return it as a solution
            else if all the groups satisfy c3
                return new-groups as the solution

    [*]add item to dictionary of solutions, key is the pair (persons, groups), value is empty
    return empty value

The decision tree will exhaust all the possible paths towards the solution. However, if you use dynamic programming you can improve the performance by avoiding the execution of already known paths. The dynamic-programming part is marked with [*] in pseudocode.

You might further improve the performance by preferring least-popular persons over most popular when grouping.

Here's a Python implementation in case anyone needs it: https://repl.it/@OzrenTkalcec/Dividing-of-K-people-into-N-groups

Disclaimer: I'm not a data scientist, but I like to solve puzzles like this one :)

HTH


Sorting a sorted array after increasing several elements I know that most of the efficient sort algorithms can run with a complexity of $O(n\cdot log(n))$, but this is given an unsorted array.

However, given that the initial array is already sorted, is there an algorithm that can sort the array after multiplying several elements by 2 (or increasing them by some value) with complexity of $O(n)$?

You can update the array using the merge procedure of mergesort. Decompose your array into two smaller arrays: unchanged elements and updated elements. Since multiplying elements by $2$ preserves their relative order, you can do this decomposition in $O(n)$ while producing two sorted smaller arrays. You can then merge them in $O(n)$.


How do I write a proof using induction on the length of the input string? In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata.  I understand mathematical induction, however when strings come into play I get real tripped up.  I'd really appreciate it if someone would go through the process of making such a proof step by step.

Here's an example problem (Exercise 2.2.10 from Hopcroft and Ullman 3rd Edition):

  Consider the DFA with the following transition table:

        0    1
       ________
-> A |  A    B
  *B |  B    A

  Informally describe the language accepted by this DFA, and prove by induction on the length of an input string that your description is correct.

This is an answered problem in the book, so I'm not looking for someone to do my homework.  I just need someone to explain it to me straight.

Book's Answer:
(taken from here)

  The automaton tells whether the number of 1's seen is even (state A) or odd (state B), accepting in the latter case. It is an easy induction on |w| to show that dh(A,w) = A if and only if w has an even number of 1's.
  Basis: |w| = 0. Then w, the empty string surely has an even number of 1's, namely zero 1's, and δ-hat(A,w) = A.

  Induction: Assume the statement for strings shorter than w. Then w = za, where a is either 0 or 1.

  Case 1: a = 0. If w has an even number of 1's, so does z. By the inductive hypothesis, δ-hat(A,z) = A. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then so does z. By the inductive hypothesis, δ-hat(A,z) = B, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case, δ-hat(A,w) = A if and only if w has an even number of 1's.
  Case 2: a = 1. If w has an even number of 1's, then z has an odd number of 1's. By the inductive hypothesis, δ-hat(A,z) = B. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then z has an even number of 1's. By the inductive hypothesis, δ-hat(A,z) = A, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case as well, δ-hat(A,w) = A if and only if w has an even number of 1's.

I understand how to prove things like $\sum_{i=0}^{n}i = \frac{n(n+1)}{2}$ using induction.  I'm just confused by how this works with building strings.  I'm confused by the bolded parts.  I don't understand how they are come up with/how it actually proves what is accepted/how it is inductive.

δ-hat is the extended transition function, by the way.

As it is unclear where your problem lies, I'll start at the very beginning.

Mathematical induction works like the game of Chinese whispers (in the ideal case, i.e. all communication is lossless) or (perfectly set up) dominoes: you start somewhere and show that your every next step does not break anything, assuming nothing has been broken till then.

More formally, every induction proof consists of three basic elements:

Induction anchor, also base case: you show for small cases¹ that the claim holds.
Induction hypothesis: you assume that the claim holds for a certain subset of the set you want to prove something about.
Inductive step: Using the hypothesis, you show that the claim holds for more elements.

Of course, the step has to be tuned such that it covers the whole base set (in the limit).

Important note: people who are confident of their induction skills often gloss over the anchor and leave the hypothesis implicit. While this is fine when presenting your work to an expert audience (e.g. a paper), this is not recommended when doing proofs yourself, especially as a beginner. Write down everything.

Consider a simple example over $(\mathbb{N},\leq)$; we want to show that $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ holds for all $n \in \mathbb{N}$.

Anchor: For $n=0$, $\sum_{i=0}^{n} i = 0 = \frac{n(n+1)}{2}$ clearly holds.
Hypothesis: Assume that $\sum_{i=0}^{k} i = \frac{k(k+1)}{2}$ holds for an arbitrary, but fixed² $n \in \mathbb{N}$.
Step: For $n+1$, compute the sum:

$\qquad \displaystyle \sum_{i=0}^{n+1} i = (n+1) + \sum_{i=0}^{n} i \overset{\text{IH}}{=} n+1 + \frac{n(n+1)}{2} = \frac{(n+2)(n+1)}{2}$

So the identity holds for $n+1$. (We note that we only needed a tiny part of the hypothesis, namely for $k=n$. That often happens.)

The inductive principle now assures us that the claim indeed holds: we have directly shown it for $0$. The step says, if it holds for $0$, it also holds for $1$; if it holds for $1$, it also holds for $2$; and so on.

Let's have a look at another example, this time on $(2^\mathbb{N}, \subseteq)$. The claim we want to prove is: for every finite subset $A$ of $\mathbb{N}$, the size of the power set $2^A$ of $A$ is $2^{|A|}$³. We perform our induction over $(\mathbb{N}, \leq)$, again, namely over the size of subsets $A$.

Anchor: Consider the (only) set of size $0$, the empty set. Clearly, $2^\emptyset = \{\emptyset\}$ and therefore $|2^\emptyset| = 1 = 2^0$ as claimed.
Hypothesis: Assume that for all sets $A \subseteq \mathbb{N}$ with $|A| \leq n$ with some arbitrary, but fixed $n \in \mathbb{N}$, we have $|2^A| = 2^{|A|}$.
Step: Let $B \subseteq \mathbb{N}$ arbitrary⁴ of size $n+1$, and let $b \in B$ arbitrary (such $b$ exists as $n+1 > 0$). Now the hypothesis applies to $B \setminus \{b\}$ and thus $|2^{B \setminus \{b\}}| = 2^n$. Since

$\qquad \displaystyle 2^B = 2^{B \setminus \{b\}} \cup \{ A \cup \{b\}\mid A \in 2^{B \setminus \{b\}} \}$,

we have indeed that $|2^{B}| = 2 \cdot |2^{B \setminus \{b\}}| = 2 \cdot 2^n = 2^{n+1}$ as claimed.

Again, by induction the claim is proven.

Now, for your problem can use a common trick: strengthening the statement. If you formulate your claim as "the automaton accepts all words with an odd number of ones", you get an induction hypothesis like "among all words of length $n$, exactly those with an odd number of ones are accepted by the automaton". This won't lead you anywhere since we don't know anything about how many ones are contained in which part of a given (accepted) word; the hypothesis does not apply on whatever you cut away of your arbitrarily selected word.

Therefore, you want to formulate a stronger claim: "The automaton is in state $B$ if and only if the consumed part of the input contained an odd number of ones", and show this one. Note that it implies the former claim.

Anchor: After processing the only string of length zero, $\varepsilon$, the automaton is clearly in state $A$ as claimed.
Hypothesis: Assume that claim holds for input fragments of length up to $n$ which is chosen arbitrarily, but fixed.
Step: Consider an arbitrary word $w \in \{0,1\}^{n+1}$. There are two cases.

$w$ contains an even number of ones. There are two cases for the last symbol.

$w_n = 0$: In this case, $w' = w_1 \dots w_{n-1}$ contains an even number of ones. By induction hypothesis, the automaton is in state $A$ after consuming $w'$. Consuming $w_n = 0$ causes the automaton to stay in state $A$, as claimed.
$w_n = 1$: In this case, $w' = w_1 \dots w_{n-1}$ contains an odd number of ones. By induction hypothesis, the automaton is in state $B$ after consuming $w'$. Consuming $w_n = 1$ causes the automaton to switch to state $A$, as claimed.

$w$ contains an odd number of ones. Similar to case 1.

The principle of induction implies that the claim indeed holds.

You perform induction along some partial order; the anchor needs to cover all minimal elements, and sometimes more (depending on the statement).
The "arbitrary, but fixed" is essential! We can not change $n$ in the step and treat it as if it were a fixed number, but we can also not assume anything about it.
Denoting the power set with $2^A$ may seem weird. It is rooted in the observation that the power set is equivalent to the set of all functions from $A$ to ${0,1}$, which is denoted thus.
Choosing $B$ arbitrary is essential for covering the whole space. One may be tempted to say, "Take any such $A$ and add an element that was not there before.". In this case, that would do the same, but it can be easy to get wrong in more complicated settings (e.g. adding nodes to graphs). Always take an arbitrary larger object and then cut it apart to apply the hypothesis on its parts; never assemble the larger object from smaller which are covere by the hypothesis.


Mutual Exclusion by disabling interrupt I am reading William Stallings operating system book which gives this pseudo-Code for disabling interrupt to achieve Mutual Exclusion

while (true) {
 /* disable interrupts */;
 /* critical section */;
 /* enable interrupts */;
 /* remainder */;
}

But I don't get why there is a While loop in the code which is true
this means that this part of the code repeats forever but why?

The while loop with true condition is just to ensure this process can enter and exit its critical section repeatedly. This usage is quite common when we are discussing concurrency programming.

Take a moment to reflect. How can you create an environment to demonstrate easily the effect of two or more different concurrent processes are, for example, contending for one shared resources? If you let each process just try to enter the critical section once, it might be hard to produce the various particular situations that could happen only to concurrent running processes. It may just happen all processes enter the critical section in order once and then exit.  However, if we use a while(true) loop to run the processes long enough, it will be much more probable to observe all sorts of phenomenons.


Prove that 2-Colourability is in L from Undir-Reachability is in L Let Undir-Reachability be the following problem:
given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G?

I need to prove that the 2-Colourability is in L, by knowing that Undir-Reachability belongs to the complexity class L.

I don't know how to start.

Hint: a graph is not bipartite if there is a walk of odd length from a vertex to itself.


Why does the BFR (Bradley, Fayyad and Reina) algorithm assume clusters to be normally distributed around its centroid? I'm following a course on data mining based on the lectures from Stanford University and the book Mining of massive datasets.

On the topic of clustering, the BFR algorithm is explained with this video.
I understand how the algorithm works, but I am unclear on the reason why the algorithm makes the strong assumption that each cluster is normally distributed around a centroid in Euclidian space.

The video explains that the assumption implies that clusters look like axis-aligned ellipses, which is understandable as the dimensions must be independent.
I've watched the video a few times, and read the section in the book (freely downloadable using the first link) on pages 257-259, but I'm unable to grasp why that assumption is made, and why it has to be made.

Could someone explain this for me?

Roughly, the algorithm needs to estimate the probability to assign a point the correct cluster.
So the algorithm add P to a cluster if it is very unlikely that, after all the points have been processed, some other cluster centroid will be found to be nearer to P.
So the algorithm measure the probability that, if P belongs to a cluster, it would be found as far as it is from the centroid of that cluster. To do that, it assumes that the clusters contain normally distributed points aligned with the axes of the used space.


Subset-sum approximation algorithm running time in 35.5 of CLRS i have read about algorithm to find sum as large as possible, but not larger than $t.$

Essential part of this algorithm is trimming. On every step you delete all numbers which close one to another, but one to represent them all.  Good explanation of the algorithm.

At page 7 from provided link or at page 1133 of ClSR 3rd edition you can find such a statement: $z'/z>1+\epsilon/2n.$ I think $z'$ and $z$ is numbers of elements before and after trimming. But i can't understand how they got such estimation. For example at first step trimming don't actually trim any element. We can devise example of sequence and epsilon to have no trimmed elements even at second step.

Can somebody, please, explain how they got such an estimation? Thanks.

Both $z$ and $z'$ belong to the same trimmed list, after trimming. The point is that after trimming, two adjacent elements are at a multiplicative distance of at least $1+\epsilon/(2n)$, by construction. This is why the trimmed lists are small, and so the running time is reasonable. If there is no trimming then there is no problem – the original list already satisfies this condition.

Here is a concrete example. Suppose we want our elements to be at multiplicative distance at least $2$, and suppose that the original list is $1,2,3,4,5,6,7,8$. After trimming we are left with $1,2,4,8$, and any two adjacent elements are at multiplicative distance at least $2$ (in this case, exactly $2$). Had we started with, say, $1,4,9,16$, no trimming would be necessary, but still adjacent elements are at multiplicative distance at least $2$.


Complexity analysis of while loop with two conditions I am curious how to do a line by line analysis of this piece of code using the "Big O" notation.

i = 0;
j = 0;

while ( ( i < n ) && ( j < m ) )
{
      //do something
      i++;
      j++;
}

How I should represent number of iterations for the loop? Is good if I will do some assumptions or I should write min(n, m)?

Small extension after @Patrick87's comment to show why I am not sure that min() is a general solution:

i = 0;
j = 0;

while ( ( i < n ) && ( j < m ) )
{
      //do something
      i++;
      j++;
}
if ( i < n )
{
      while ( ( i < n ) )
      {
         //do something
         i++;
      }
}
else
{
      while ( ( j < m ) )
      {
         //do something
         j++;
      }
}

How right now we can connect a number of iterations of the first loop and second one if we don't know which condition broke the condition of the first loop?

As Patrick87 pointed out. The first loop is $\min(m,n)$.  As for your extended question,   it's unclear if you want best, worst, or average case.  We typically look at worst case.  Either way, you seem to be focused on a single execution when you really need consider all possible $i$ and $j$ values.  So, let's do that:

$m = n$.

In this case the additional conditional does no work, so the total run time is still $O(\min(m,n))$.

$m < n$.

When this is true, then the first loop terminates due to $j$. The conditional will then carry out the first case $i < n$ and terminate after $O(n-m)$ iterations.  The total number of operations is then $O(n-m+m)= O(n)$ operations.

$m > n$.

This case is equivalent to the second case but the result is $O(m)$.

Now observe that cases 1,2, & 3 are all equivalent to $O(\max(m,n))$. This is the running time for your code.

So back to your "how to" question. You need to do a good, thorough case analysis for multi-conditional loops just like you need to do with conditionals.  Then analyze the running time of each case and, assuming your doing worst case analysis, take the largest running time.


Counting substrings that belong to a regular language Given a regular language $L$ and a string $x$ give an efficient algorithm to count the occurrences of substrings $x[i,j] \in L$.
More in particular, I am looking for a linear time algorithm in the length of the string $|x|$, for a given deterministic automaton $M$ accepting the language $L$.
This question is meant to generalize the question of counting substrings where each symbol occurs an even number of times, asked before here.

You can do it in $O(|x|\cdot |M|)$ with dynamic programming.
Let $q_0$ be the starting state, $\delta$ the transition function of $M$, and $a(q) \to \{0, 1\}$ a boolean function indicating whether $q$ is an accepting state in $M$.
Let $A[i, q]$ be the number of non-empty prefixes of $x_ix_{i+1}\ldots x_n$ accepted by $M$ if we start in state $q$. We can directly compute $A[n, q] = a(\delta(q, x_n))$. Then, going backwards row by row, we can fill the table using $A[i,q] = a(\delta(q, x_{i})) + A[i+1, \delta(q, x_{i})]$.
Finally, you sum $a(q_0) +\sum_{i=1}^nA[i, q_0]$ as your answer, as this is the sum over all non-empty prefixes of all non-empty suffixes, plus one if the empty string is accepted, thus all substrings.


Cache Miss and Processor Speed today in my class my professor mentioned that
Cache misses becomes more expensive as the speed of the processor increases

But he didn't explain the reason. I searched this statement over the internet and found no answer whatsoever.
According to me, this statement is true because, when the speed of the processor increases it can execute more instructions at a given clock cycle, thus a miss leads to a stoppage of more instructions from executing. So cache misses becomes expensive as processor speed increases. Is my thinking correct or am I doing it all wrong?

Yes, that's correct. Assuming the speed of the cache doesn't change, a cache miss takes a fixed amount of time, and if the number of instructions per time unit increases, then more instructions get delayed because of the cache miss.
Modern processors try different methods to counteract this. Obviously you can use bigger caches which may lead to fewer cache misses. The disadvantage is that with the same technology, a bigger cache will run slower. Another method is organising the cache in such a way that "normal" code doesn't produce unneeded cache misses.
Another method is "streaming", where the cache figures out that you are reading from consecutive memory addresses, and uses this to start loading data before it is needed, reducing the average cost of a cache miss. That is often automatically. There may be instructions that load data from memory without caching it - if you process a gigabyte of data in consecutive memory, then caching any of it is pointless.
Then comes out-of-order execution: You may have one instruction waiting because of a cache miss, but other instructions not affected by this can go on executing. And with hyperthreading the processor executes two or more threads interleaving instructions; if thread A has to wait, then thread B continues at full speed.


A two-tape deterministic Turing machine that recognizes an exponential string How can I describe a Turing Machine recognizing the language $P=\{a^{2^n} | n \geq 0 \}$?

This Turing Machine is deterministic and uses two tapes, both bidirectional and R / W (read & write)

The computation should be done in linear time.

I've read Counters in Turing machines but it doesn't address my question. It can help but it doesn't answer my question.
Turing Machines with $n$-tapes have the same computability that Turing Machines with one tape, but different behavior. Here I'm asking about the behavior of a two-tape TM.

My approach:

I think I may use the first tape as input tape and copy every character in the second tape. But I don't know how to keep track the exponential behavior.

To expand fade2black's answer; this is a simple proof by induction that the following TM

State    Symbol    Write  Move   Newstate
start    0         1      L      tolsb
start    1         0      R      carry

tolsb    _         _      R      start
tolsb    *         *      L      tolsb

carry    0         1      L      tolsb
carry    1         0      R      carry

performs a binary count from $0^n$ to $1^n$ in less than $2^{n} + n^3$ steps.
Initially the head is placed on the LSB (which, we assume, is on the left part of the input string).

You can view a simulation of the Turing machine here.

We prove by induction that starting on the leftmost $0$, it counts up to $1^n$ and, at the end, the head is still placed on the LSB.

case $n = 1$:

Immediate

 _ 0    start
   ^
 _ 1    step 1
 ^
 _ 1    step 2
   ^

case $n$: suppose that it holds for $n-1$; i.e. it can count up from $0^{n-1}$ to $1^{n-1}$ in less than $2^{n-1} + (n-1)^3$ steps;

Then after less than $2^{n-1} + (n-1)^3$ steps the head is on LSB:

   1 2 3 ...   n
 _ 1 1 1 ... 1 0
   ^

It will convert all $1$s to $0$ and propagate the carry to the MSB and convert the MSB to $1$ in $n$ steps:

   1 2 3 ...   n
 _ 0 0 0 ... 0 1
             ^

Then it will go back to the LSB in $n$ steps

   1 2 3 ...   n
 _ 0 0 0 ... 0 1
   ^

Then it will count up to $1^n$ using less than $2^{n-1} + (n-1)^3$ steps.

   1 2 3 ...   n
 _ 1 1 1 ... 1 1
   ^

The total number of steps is less than:

$$2^{n-1} + 2^{n-1} + 2(n-1)^3 + 2n \leq 2^n + n^3$$

So if we have as input $w = a^{2^n}$; we can perform a binary count (on the second tape) in linear time $O( |w| )$.


Error in the Algorithm Design Manual? Take a look at this excerpt from the Algorithm Design Manual, 2nd Edition by Skiena.

I have circled the confusing bit. Basically, everything is understandable to me, until that part. How can $Increment([m+1/2])$ be rewritten as $Increment([m])$? Clearly, if m is an integer, then the algorithm will not treat $m+1/2$ as $m$ and return $m+1$. Instead, $Increment$ is going to go into the $else$ clause and return $m+1/2+1$, which is clearly not $m+1$. Am I missing something here?

How can $Increment([m+1/2])$ be rewritten as $Increment([m])$?

Recall that $[x]$ means the greatest integer less than or equal to $x$.

Since $m$ is integer, $m$ is the less than $m+0.5$ and $m+0.5 < m+1$. Thus the the greatest integer less than or equal to $m+0.5$ is $m$.


What is the name for closure-type functions that use the call-site environment? Closures are functions that borrow the environment in which they are declared and can use and modify its variables at any times indipendently from where they're called, like in this example:

function createclosure(x)
    return function() --Anonymous closure
        print(x) --The variable x is caught and can be used anywhere
    end
end

myclosure = createclosure(123)

myclosure() --prints "123"

What I am looking for is quite the opposite: functions that borrow the environment in which they are called and can use and modify its variables:

function anti_closure()
    x = x + 10 --x is borrowed from the environment in which the function is called
    print(x)
end

function environment(x)
    print(x)
    anti_closure()
    x = x - 5
    print(x)
end

environment(23) --prints "23", "33" (from the anticlosure) and then "28" (because x was permanently modified in the anticlosure)

Is there a name for these type of functions? Are there languages that implement them? If not, why?

You are talking about static vs. dynamic scoping of variables. Most langauges today have static scoping, but famously the early LISP had dynamic scoping.

Scoping is a general feature of a programming language and is not something that a closure does (although I suppose one could organize things so that it does). In any case, look up "dynamic" and "static" scoping.


Prove that $(uv)^R = v^Ru^R$ The reverse of a string, introduced informally above, can be defined more precisely by the recursive rules $$a^R=a,$$ $$(wa)^R=aw^R,$$ for all $a \in \Sigma$, $w \in \Sigma^*$. Use this to prove that $$(uv)^R = v^Ru^R,$$ for all $u, v \in \Sigma^+$.

This is exercise 3 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. I am not used to this type of exercise, so I would like some help to get the hang of it.
My attempt: Suppose $u = u_1...u_n$ and $v = v_1...v_n$. So, $$(uv)^R = (u_1...u_nv_1...v_{n-1}v_n)^R = v_n(u_1...u_nv_1...v_{n-1})^R \implies (uv)^R = v^Ru^R.$$
Is it correct? If not, any hint? Thanks in advance.

The answer depends on your standard of proof. Let's try to be very strict.
First of all, let us define words. In contrast to Peter Linz, we will not be afraid of the empty string. The set of words $\Sigma^*$ satisfies the following:

If $w \in \Sigma^*$ then either $w = \epsilon$ or $w = x\sigma$, where $x \in \Sigma^*$ and $\sigma \in \Sigma$.
$\epsilon \neq x\sigma$ for every $x \in \Sigma^*$ and $\sigma \in \Sigma$.
$x\sigma = y\tau$ iff $x=y$ and $\sigma=\tau$.
Define an inductive subset of $\Sigma^*$ to be a subset $S \subseteq \Sigma^*$ such that (i) $\epsilon \in S$ and (ii) if $x \in S$ then $x\sigma \in S$ for all $\sigma \in \Sigma$.

$\Sigma^*$ is an inductive subset.
If $S$ is an inductive subset then $S = \Sigma^*$.

Now we can define concatenation of words inductively:

$w.\epsilon = w$.
$w.(x\sigma) = (w.x)\sigma$.

Finally, we define reversal:

$\epsilon^R = \epsilon$.
$(x\sigma)^R = \sigma.x^R$, where $\sigma$ is syntactic sugar for $\epsilon \sigma$ (which we know to be in $\Sigma^*$ since it is an inductive subset).

We need several lemmas.
Lemma 1. For all $x \in \Sigma^*$, we have $\epsilon.x = x$.
Proof. Let $S = \{ x \in \Sigma^* : \epsilon.x = x \}$. We will show that $S$ is an inductive subset, and so $S = \Sigma^*$, that is, $\epsilon.x = x$ for all $x \in \Sigma^*$.
If $x = \epsilon$ then $\epsilon.\epsilon = \epsilon$. If $x = y\sigma$, where $y \in S$, then $\epsilon.x = \epsilon.y\sigma = (\epsilon.y)\sigma = y\sigma = x$, using $y \in S$. $\square$
Lemma 2. For all $x,y,z \in \Sigma^*$, $x.(y.z) = (x.y).z$.
Proof. Fix $x,y \in \Sigma^*$, and let $S = \{ z \in \Sigma^* : x.(y.z) = (x.y).z \}$. We will show that $S$ is an inductive subset, and so $S = \Sigma^*$.
If $z = \epsilon$ then $x.(y.z) = x.y = (x.y).z$.
Now suppose that $z = w\sigma$, where $w \in S$. Then
$$
x.(y.z) = x.(y.w\sigma) = x.((y.w)\sigma) = (x.(y.w))\sigma = ((x.y).w)\sigma = (x.y).(w\sigma) = (x.y).z,
$$
using $z \in S$. $\square$
Now we are ready to prove your claim.
Fix $x \in \Sigma^*$, and let $S  = \{ y \in \Sigma^* : (x.y)^R = y^R.x^R \}$. We will show that $S$ is an inductive subset, and so $S = \Sigma^*$, that is, $(x.y)^R = y^R.x^R$ for all $y \in \Sigma^*$.
If $y = \epsilon$ then
$$ (x.y)^R = x^R = \epsilon.x^R = \epsilon^R.x^R, $$
using Lemma 1.
If $y = z\sigma$, where $z \in S$, then
$$ (x.y)^R = (x.(z\sigma))^R = ((x.z)\sigma)^R = (\epsilon\sigma)^R. (x.z)^R. $$
Let us notice that $(\epsilon\sigma)^R = \epsilon\sigma.\epsilon^R = \epsilon\sigma.\epsilon = \epsilon\sigma$. Also, since $z \in S$, $(x.z)^R = z^R.x^R$. Therefore
$$ (x.y)^R = (\epsilon\sigma).(z^R.x^R) = ((\epsilon\sigma).z^R).x^R = (z\sigma)^R .x^R = y^R.x^R.$$
using Lemma 2. $\square$

While I tried to be rather strict, a completely formal proof will be even stricter: it will justify every single step, referring to a definition, a lemma, or a logical axiom. However, the proof above should be easy to convert to something that proof assistants can grok.

In practice, you can prove your claim as follows. Let $x = \sigma_1 \ldots \sigma_n$ and $y = \tau_1 \ldots \tau_m$. Then
$$
(xy)^R = (\sigma_1 \ldots \sigma_n \tau_1 \ldots \tau_m)^R = \tau_m \ldots \tau_1 \sigma_n \ldots \sigma_1 = (\tau_m \ldots \tau_1) (\sigma_n \ldots \sigma_1) = y^R x^R.
$$
At a more advanced stage, this proof can be summarized by "obvious".


DFS on reversed graph I was watching a lecture on determining the strongly connected components of a graph using Kosaraju's algorithm and the lecturer claimed one can easily walk the edges in reverse fashion.

While I see this happening with an adjacency matrix representation(the reverse is the matrix transpose, and you can determine its elements on demand), I'm having a hard time coming up with a solution in the case of the adjacency list representation.

Any hints?

You can iterate over all of the edges in $O(|E|)$ time.  So, construct a copy of the graph with reversed edges as follows: iterate over all the edges, and as you examine each edge, add the reversed edge to the copy.  That takes $O(|E|)$ time in total, and you only need to do it once, as a pre-processing step.  Now, during Kosaraju's algorithm, if you ever need to walk edges in a reversed fashion, you can just refer to the reversed graph you created earlier.


Is it possible to wear-level a FAT32 file system? Because SD cards use flash memory, they should requires wear leveling to avoid significantly shortening the life of the card. At the same time, my understanding is that they usually use a FAT32 file system.
My understanding of FAT32 is that there is a small "file system description" block at the beginning of the device, which is followed by the file allocation table (FAT) describing which files are stored where. However, because the FAT needs to be updated every time a file is moved/copied/appended/etc, then doesn't that mean the FAT gets written to many times more often than the rest of the card?
For example, if each erasable block of an SD card is 4 KB, and it uses a 32-bit address space, they each erasable block of the FAT contains 128 addresses, so the FAT should get erased and written ~128 times as often as the rest of the device. If this hypothetical device has an expected life span of >100k cycles, then should it not wear out around 1k cycles if it spends the entire time formatted with a FAT32 file system?
And, if my current understanding is true, then wouldn't FAT32 be basically the worst possible way to format a flash memory device? Or is this a problem that all file systems have, so FAT32 isn't apreciably worse than anything else?

The OS references blocks using a "logical block address".  The SD card then maps this to a physical page of flash memory.  With wear leveling, each time data in that block is changed, it will get mapped to a new physical page of flash memory.  So, even though the OS is changing the same "logical block address" every time, this is causing different physical pages in flash to be erased and rewritten.  This spreads out the "wear" across the entire flash device, lengthening its lifetime and avoiding the problem you mentioned.  In other words, although the FAT32 is stored at the same "logical block address", it isn't stored on the same physical page of flash memory every time it is modified.
I'd expect that any commercial flash storage device you buy today will be using wear leveling, because of exactly the problem you mention if wear leveling isn't used.  This problem is not specific to FAT32; it occurs with essentially all conventional filesystems.


Comparing asymptotic notations I have a problem P that is said to be O(n^7) in the worst case.
I'm asked to agree or not if it is solvable in O(n^9) time. And also I'm asked to agree or not if P cannot be solved faster than Ω(n^7) in the worst case.

My answer for the first question is that if P is bounded by O(n^7) it is also solvable in O(n^9).

And for the second question: Ω(n^7) means that the running time cannot be less than n^7, but we already know that P is bounded by O(n^7) in the worst case and it is not proven that it can't be solved faster, so I think this statement is false.

So my questions are: how do I prove the answer for the first question and how do I express my second answer in terms of functions?
I've seen a lot of info about asymptotic notations, but I couldn't find any info that could enlighten me how to answer the questions I am asked.

Thanks.

If P is solvable in $O(n^7)$, that means that P is solvable in $C \cdot n^7$ time, for some constant $C>0$ and large enough $n$. Since $C \cdot n^7 < C \cdot n^9$ for large enough $n$, that implies that P is solvable in $O(n^9)$.

P is bounded by O($n^7$) in the worst case, but it does not imply that in the best case cannot run in constant time, for instance. Thus, P is not greater than $C \cdot n^7$ for large enough $n$, so it is not $\Omega(n^7)$.


Unification with a list of terms The problem: we have a list of terms $[t_1, ..., t_n]$ , and a term $t$, and we want to find which of the terms in the list can be unified with $t$. Obviously we can iterate through the list and check one-by-one whether $t_i$ unifies with $t$, but what better (i.e. faster) approaches exist? Assume we can store the list however we want.
I'm particularly interested in approaches that extend well to unification modulo a theory, but assume the empty theory to start.
This must be a basic question but I can't find good references, so any references are much appreciated.

Prolog compilers already do this. Imagine if you had the program:
p(t1) :- body_1.
p(t2) :- body_2.
% ...
p(tn) :- body_n.

and you issued the query p(t).
There is a lot of literature on this topic, and I don't know if there is a recent review which covers it all. You could start with:
Colomb, J. Enhancing Unification in Prolog through Clause Indexing, J. Logic Programming, 1991:10:23-44.


Subset optimization problem Consider we have a finite set $S$ with $n$ distinct elements. We want to find a subset $\{a_1, a_2, \dotsc, a_k\}\subseteq S$ ($k\ll n$) such that a function $f(a_1,a_2,\dotsc,a_k)$ is maximized. Consider $f$ to be a symmetric function that takes $k$ arguments.

More specifically, we are given $n = 120$ items, each item being associated with three positive numbers $(A_i, B_i,C_i)$, and we want to choose $k=12$ items within this set such that

$$ \frac{\sum_{k=1}^{12} A_{i_k} \times \left\lceil\frac{\sum_{k=1}^{12} B_{i_k}}{10000}\right\rceil}{\sum_{k=1}^{12} C_{i_k}} $$

is maximal.

If we solve it by exhaustive search it requires $\binom{120}{12} \approx 10^{16}$ operations. Is there faster method to this problem? Approximate solution is also fine.

Here are some crazy ideas, with absolutely no guarantee that they'll find a good solution -- but ideas you could try.

One possible heuristic approach might be to use quadratic programming combined with randomized rounding and some more heuristics.

In particular, introduce variables $x_i$ (for $i=1,2,120$); the idea is that $x_i=1$ means that $i$ is one of the 12 items you select, and $x_i=0$.  Now we have linear constraints $0 \le x_i \le 1$ and $x_1+x_2+\dots+x_{120} = 12$.  We could fix some constant $U$, introduce the constraint $\sum_i C_i x_i \le U$, and maximize the quadratic function $(\sum_i A_i x_i) \times (\sum_i B_i x_i)$.  Now the values of $x_i$ you get back won't necessarily be 0 or 1 (they'll probably be fractions), but you could use randomized rounding to convert it to a 0/1-solution.  Now sweep over a range of possible values of $U$ (increasing each time by a multiplicative factor of, say, 1.1 times the previous value), and keep the best solution you find.

This might work, or it might not, but it's something you could try.

You could also try formulating this as a semidefinite programming problem or quadratic programming with quadratic constraints (with each $x_i$ representing whether you take item $i$ or not), then apply randomized rounding to account for the fact that the $x_i$'s should all be 0 or 1.  In particular, if you work on the decision problem (does there exist a solution whether the objective function exceeds $r$?), then you can phrase everything using quadratic constraints -- the requirement that $(\sum_i A_i) (\sum_i B_i)/(\sum_i C_i) \ge r$ is equivalent to $(\sum_i A_i) (\sum_i B_i) - r (\sum_i C_i)$, which is a quadratic function in the $x_i$'s.  You might be able to express this as a semidefinite programming problem.

Another heuristic might be to try splitting this into sub-problems and then trying to merge, using a divide-and-conquer style approach.

Randomly partition the 120 items into two sets of 60, namely sets $L,R$ such that $|L|=|R|=60$ and $L\cup R=\{1,2,\dots,120\}$.  Enumerate all $60 \choose 6$ ways to choose 6 items from $L$, and compute the value of $(\sum A_i) (\sum B_i)/(\sum C_i)$ for each such subset of 6 items.  This gives you a list of ${60 \choose 6} \approx 2^{26}$ different 6-subsets, and a $U$-value for each.  Sort that list by decreasing value.  Do the same for $R$.

Now try to combine these two lists.  For instance, you could throw away all but the top 5% of each of the two lists, then try all ways of pairing up one subset of 6 items from the first list with one subset of 6 items from the second subset; compute the value of your objective function for each such subset of 12 items, and keep track of the best you've seen so far.

Repeat many times with many different ways of partitioning the 120 items into two sets of 60.

Again, I have no clue whether it will work well or not.  There's no reason to believe it will necessarily give the best solution.