Given a relation and asked to enumerate all FD's and mark the trivial FD's Given a relation R(A,B,C) and a FD set (A->B, B->C), find the FD Closure. Enumerate all the FD's and organize them accordingly to the LHS of the FD's. Mark all the trivial FD's.

I am a little confused with the second part of the question and don't understand what exactly they mean by "organize them accordingly to the LHS of the FD's"
My understanding is, Apart from the given FD's, we have A->C(on account of transitivity) and the trivial FD's will be A->A , B->B, C->C, A->AB, A->AC, B->BC. Is this the answer to the given question or am I missing something here?

I suppose that in the exercise, the request “organize them accordingly to the LHS”, is just a request of sorting all the functional dependencies (maybe lexicographically) with respect first to the attributes of the left hand side (the determinant of the functional dependency) (and then maybe on the rigth hand side for all the FD with the same left part).

For what concerns the list, I think it should include all the possible functional dependencies, including those with two attributes as determinant, as well as the (only) dependency with three attributes as determinant, as well as those with all the subset of attributes determined on the right part. So something like:

A -> A
A -> AB
A -> AC
A -> BC
A -> ABC
AB -> A
...
B -> B
...

If you want to be super-formal, you can include also the trivial dependencies A -> {}, etc., as well as the trivial dependency {} -> {}.


A modified version of two way DFA Following an exercise from Hopcroft-Ullman's Introduction to automata theory:

Let's define $k-MDFA$ as two way deterministic finite automaton with $k$ markers, similarly to two way $DFA$ but with ability to place (or pick up) a marker on the input cell currently under the head, but with limitation to placing at most $k$ markers at any time during computation, and with single cell only being able to hold at most 1 marker at any given time.

Formally, it's a tuple $A=(Q, \Sigma, \delta, s, F)$ where

$Q$ is finite set of states
$\Sigma$ is the input alphabet
$\delta : Q \times (\Sigma \hspace{2pt}\cup \hspace{2pt} \{\vdash, \dashv\})\times \{0,1\} \rightarrow Q \times \{\textbf{L,R}\}\times \{0,1\}$ is the transition function
$s$ is the initial state and $F$ is the set of accepting states

Input tape of the automaton for word $w \in \Sigma^*$ is $\vdash w \dashv$.

Moreover the transition function satisfies $\delta(q,\vdash,m) = (q', R, m')$,  $\hspace{2pt}\delta(q, \dashv, m) = (q', L, m')$ for all $q \in Q, \hspace{2pt} m \in \{0,1\}$ and for some $q' \in Q $ and $m' \in \{0,1\}$ (we do not allow automaton to leave the input).

If automaton attempts to place more than $k$ markers on the tape, the computation stops with rejection.

I have proved that $1-MDFA$ recognize exactly regular sets, but I can also show that with $2-MDFA$ I can recognize language $\{ ww : w \in \Sigma^*\}$, which is not a context free language. The second fact is fairly simple - here's an outline of how such automaton would work:

Check parity of input's lenght
Locate the middle of input by placing markers at both ends of the word, and then moving them one step closer towards the middle alternatingly.
Place marker on the first cell of input and on first cell of second half of the input
Compare letters under markers, if they differ enter reject state, if they are same, move both markers 1 step to the left and repeat. If you are about to move right marker onto symbol $\dashv$ enter accept state.

As such, clearly languages recognized by $k-MDFA$ are not contained in $CFL$ for $k \geq 2$.

My questions are:

Does increasing the amount of markers increase the computation power of $k-MDFA$ for $k \geq 2$?
Does allowing nondeterminism increase computation power of $k-MDFA$?
Can $k-MDFA$ recognize all context-free languages? If so, what's the minimal $k$ capable of expressing $CFL$?

Any references are welcome, if the question shows ignorance in the subject, I apologise.

To answer your first question, see: Burkhard Monien,
Two-way multihead automata over a one-letter alphabet.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1980) https://eudml.org/doc/92118

".. we show that for languages over a one-letter alphabet two-way automata with $k+1$ heads are more powerful than two way automata with $k$ heads."

This improves over a similar result of the same author and others for two-letter alphabets, one-way automata, or stepping from $k$ to $k+4$-heads, see the paper.

Also an interesting quote "It is wellknown that SPACE(log n), the class of languages acceptable within space bound log n, is identical with the class of  languages acceptable by two-way multihead automata".


Does BNF terminate on a first match? I know that the grammar

<expr> = <expr> + <expr> | <num>
<num> = 0|1

is ambiguous because it cannot decide between (1+1)+1 or 1+(1+1).  However, that would also mean that

<expr> = <expr> + <num> | <expr> * <num> | <num>
<num> = 0 | 1

would also be ambiguous because it couldn't tell if 1+1*1+1 is (1+1)*(1+1) or ((1+1)*1)+1.  Or does it distinguish between these by terminating the interpretation as soon as it finds one match?

If it does terminate on a first match, then would 1+1*1+1 necessarily get interpreted as the first option since it is possible to interpret the "main operation" as being +?

You can't match 1+2*3+4 with expr * num because 3+4 isn't a num. The only possible match is expr + num, with 1+2*3 as the expr and 4 as the num. To make 1+2*3 an expr, you need to match it with expr * num, and then you can match 1+2 with expr + num. Finally, you can match 1 with num to make the innermost expr.

So the only possible parse is ((((1)+2)*3)+4) and the grammar is not ambiguous.

It is not the grammar we usually use for algebra because it produces an undesired parse, not because it is ambiguous.


Equivalent DPDA that always halts for every DPDA with empty stack language I want to show that for every deterministic pushdown automaton with the language of the empty stack there is a deterministic pushdown automaton that always halts.
my transition function of $P$ is

$\delta: \Gamma \times Q \times \Sigma_\lambda \to \Gamma^* \times Q$

I tried to use look ahead pushdown method. I think I should create a $DFA$ for every $q \in Q$ that recognize if $P$ is in the lambda-cycle starting from $q$ with input string reversing of containing the stack of $P$. I define NFA with states of set $\Gamma \times Q$ and it has transition from $(\alpha,p)$ to $(\alpha',p')$ reading $\beta$ if there is $(\beta\alpha',p') \in \delta(\alpha,p,\lambda)$ and start state is $(Z_0,q)$ and I think every state should be final state. then reverse $NFA$ and convert it to $DFA$. I don't know this works or not. I after that I can create $DPDA$ named $P'$ such that its stack simulate all $DFAs$ and also original stack of $P$ and after that I can decide if $P$ will be in the loop in future so in $P'$ it halts.

how can I edit creating $DFA$ that works well?

Edit

I changed the way using above automata, first of all, I design $DFA$ to check if in future there is a sequence of lambda-transitions that empties stack? if there is so I should let process continues because it will stop in future. $NFA$ is like above example with final states in $(\lambda,q)$ for each $q\in Q$ and simply we can convert $NFA$ to $DFA$, if there is not such sequence I ask another question, is it possible that we have some non-lambda transition? checking this is also simple we create exactly same $NFA$ as above $NFA$ and after that, if in a state we have non-lambda transition we go to a special final state. if there is no such transition it means we will stock on loop in future.

The look-ahead property for pushdown automata is that a PDA $Z$ can answer certain questions of the form "how would PDA $X$ behave when given my stack", and then make moves based on that information. In particular, also deterministic PDA $Z$ can use this even when $X$ is nondeterministic.

You know, as I understand from the formulation of your question, this is possible because the property "when started on stack $\alpha$ PDA $X$ empties its stack" defines a regular set of stacks. The PDA look-ahead test can then be build in the original PDA.

So, to solve your problem, you have to formulate which PDA tests you would like to perform on the stack in order to avoid infinite computations.

I do not know whether it is necessary to actually construct the regular language of stacks that gives a positive answer.


How to call something that can be either a terminal or a nonterminal? I had written a compiler compiler a few years ago and I'm now cleaning it up, improving it, and turning it into C.

I came across a terminology problem however that I remember in the past I couldn't solve it either.

Imagine an LL(k) stack. In this stack, you may have terminals, that are expected to be matched with the next token, or non-terminals that would expand based on the next token. In either case, there is a string in the stack.

The word I am looking for, is a term that means either a terminal or non-terminal. Wikipedia was of no help.

To clarify a bit more, imagine a grammar with $t = \{a \mid a \text{ terminal}\}$ and $T = \{A \mid A \text{ non-terminal}\}$. If you have a set $X = \{x | x \in t \vee x \in T\}$, how would you refer to an element of $X$? "Grammar symbol"? "Grammar element"? "Terminal or non-terminal symbol"?

I am in particular looking for a name as short and to the point as possible, since this will end up becoming a variable name!

The long forms "terminal symbol" and "nonterminal symbol" suggest that you are dealing first and foremost with "symbols"; "terminal" and "non-terminal" are qualifiying attributes that specify a symbol's role in the grammar. A symbol that can be either one of terminal and non-terminal is, almost by virtue of logics, just an arbitrary symbol.

Therefore, "symbol" seems to be the natural choice. I am pretty sure it is the term usually used, too, but such statements are hard to validate.

If you want to stress that a given symbol can be either kind (in text), you can always use "arbitrary symbol (of grammar $G$)", or define $X \subseteq t \cup T$ explicitly. In source code, I'd just use "symbol".


Insertion of n consecutive keys in an initially empty B-Tree Consider this question ( 18.2-4 of CLRS) which states that:

Suppose that we insert the keys ${1,2,...,n}$ into an empty B-Tree with minimum degree 2. How many nodes does the final B-tree have?

My approach:
We add each element one by one. We'll need 3 elements at first (namely 1,2 and 3), after which the $4th$ element will cause a split. This split is  a root node split.
A normal node split results in one extra node.
A root node split results in 2 extra nodes.
Thus after the 4th element we have 3 nodes in total. Now, as we keep on adding more elements to the B-tree, we can see a pattern in splitting. 3 lower level splits initially produce a higher level split, and then each higher level split will require 2 splits only. Since we've to approximate only, we can disregard the initial 3 split condition and go on with the 2 lower level splits to produce an upper level split.
Notice that there is atleast a split at the insertion of these elements: $4,6,8,10,12...... $
That are all even numbers leaving 2.
Thus total such splits are $n/2$
Total higher level  splits are thus:$n/4$
Total splits for the higher level than the previous one: $n/8$
Thus the total splits until the $nth$ element is inserted in the B-Tree is:
$n/2+n/4+n/8+......$
Which results in $n$.
This is more than expected. I've made two approximations here:
1)  Number of higher level splits is equal to half of the immediate lower level splits.This increases our answer.
2)  Some starting elements don't contribute to the splits.
Maybe these are the reasons why the answer is coming more. I can't enumerate these values exactly. Finding these values exactly would help me very much. Any help appreciated.
Moon

We know that every node except the root must have at least t−1=1 keys, and at most 2t−1=3 keys. The final tree can have at most n−1 nodes when n≥2. Unless n=1 there cannot ever be n nodes since we only ever insert a key into a non-empty node, so there will always be at least one node with 2 keys. Next observe that we will never have more than one key in a node which is not a right spine of our B-tree. This is because every key we insert is larger than all keys stored in the tree, so it will be inserted into the right spine of the tree. The fewest possible number of nodes occurs when every node except the deepest node in the right spine has 2 keys and the deepest node in the right spline has 3 keys. So at height 1, 1 nodes, at height 2, 3 nodes, …, at level h, 2h−1 nodes. In this case, n =2^(h+1)−1 where h is the height of the B-tree, and the number of nodes in B-Tree is #nodes = 2^(h+1)−2−h = n−lg(n+1). So for any n, the final B-Tree must have n−⌊lg(n+1)⌋≤#nodes≤n−1 (if n≥2).


Why are decision problems easier than the equivallent optimization problems? Suppose that we have an optimization problem defined as follows:

$OPT$ = Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$

and the equivallent decision problem

$L_{OPT}$ = Given an input string defining $F$ and $f$ and a target value $u\in Q$, decide if there is a solution $x \in F$ so that $f(x) \geq u$

Assuming that an efficient solution here is defined as an algorithm that runs in polynomial time in the length of the input, then if we have an efficient solution for $OPT$ it is trivial to see that we can get an efficient solution for $L_{OPT}$. However, my teacher said that we could have that $L_{OPT}$ has an efficient solution without $OPT$ having an efficient solution.

How is the latter possible? If we can efficiently solve $L_{OPT}$, wouldn't we be able to run a binary search algorithm to find the solution for $OPT$?

If the objective function $f$ is easy to compute, you can use a solution to $OPT$ to solve $L_{OPT}$: find some $x$ which maximises the objective function; compute $f(x)$ and output "yes" if it meets or exceeds the threshold $u$ (output "no" otherwise).

That is, $L_{OPT}$ reduces to $OPT$ (for some suitable definition of the reduction type), and is in this sense easier.

If we let $OPTVAL$ be the function problem of computing the optimal value, but not the solution which has this value, $OPTVAL$ reduces to $L_{OPT}$ via binary search.  (Also $OPTVAL$ reduces to $OPT$: compute the optimal solution, then compute its value.)

Note that the reduction in one direction is a member of a smaller class of reductions than in the other: when solving $L_{OPT}$ via $OPT$ you have the reduction $r$ and some post-processing $p$ such that for every instance $i$, the answer to $L_{OPT}$ equals the output of $p(OPT(r(i))$.  That is, it's a one-call reduction (but not tail call, which it can't be due to a type mismatch).  The reduction from $L_{OPT}$ to $OPTVAL$ is a multi-call reduction (with binary search it will make a logarithmic number of queries).

It's not clear to me that you can reduce $OPT$ to $OPTVAL$, not even with multiple calls: given an oracle which tells you what the optimal value is, how to you compute a solution with that value, generically?

However, most "natural" problems will probably let you do this.  For instance, if we represent a graph $G$ as the number of vertices followed by an enumeration of the complement of the edge set and want to compute the chromatic number (smallest $k$ such that the graph is $k$-colourable), we can let $G'$ be $G$ with an edge added and ask our $OPTVAL$-oracle what the optimal value is.  Whenever such a change doesn't increase the number of colours required, we learn of an additional constraint we can impose.  Do so until it's no longer possible (at most polynomially often); now each vertex is adjacent to every vertex of any different colour, i.e. $u$ and $v$ have the same colour for every $(u, v) \in (V \times V) \setminus E$. Assign a colour to an uncoloured vertex, apply this rule and repeat until the graph is $k$-coloured.

One could generalise this: let solution-extractable optimisation problems be those such that with oracle access to the optimal value on smaller instances and the given instance, you can compute the optimal solution.  Then you can multi-call reduce $OPT$ to $OPTVAL$ on solution-extractable problems (by construction).  Of course, you can also compute optimal solutions to the smaller instances, since they are instances of a solution-extractable problem by assumption; maybe that helps to extract the optimal solution to the bigger instance.

It would be nice to have some generic constructions that enable this.  Here's one idea:

Given some optimisation problem $P$ with a bound $k$ on the solution length, let instances of $Q$ be triples $(x, 1^{2k-l}, p)$ where $x$ are $P$-instances and $p$ has length $l$ be the problem of finding optimal solutions to $P$ which have $p$ as a prefix. If you can solve $OPTVAL_Q$ then $P$ is solution-extractable: whenever $OPTVAL$ of $Q$ goes down both when you extend $p$ with a $0$ and when you extend it with a $1$, $p$ is a longest optimal solution; otherwise, extend $p$ with any value which doesn't decrease the objective function.  Note that padding the problem with a number of ones equal to two times the bound on the solution length, we make the self-reductions downward when extending $p$.

Probably bit-by-bit solution extraction can be extended to chunk-by-chunk extraction if chunks have length at most $O(\log n)$ (since there's only polynomially many values to try out).


Proof of Lower Bound for Deterministic Distinct Elements Algorithm There is a proof in this document (page 8, Section 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) that mirrors a proof my professor gave in my algorithms class. The lemma states:

Suppose that there is a deterministic exact algorithm for counting distinct elements that uses o(min{|$\Sigma$|, $n$}) bits of memory to process a stream of $n$ elements of $\Sigma$.
Then there is a compression algorithm that maps $L$-bit strings to bits strings of length o($L$).

The conclusion is false, therefore the premise is false. The proof is by contradiction. This is proved by constructing a compression algorithm that encodes an $L$-length bit string in fewer than $L$ bits. A decoding method is then given for reconstructing the $L$-length bit string.
What confuses me is that the paragraph above is apparently the contradiction that proves that you cannot transmit an $L$-length bit string using fewer than $L$ bits. And yet it seems to show that this actually can be done.
I understand the counting argument that says you cannot map $2^L$ bit-strings losslessly onto a range of $2^L-1$ outputs. What I need to understand for my class is why the given proof by contradiction is valid. If anyone can help me with the intuition concerning why the proof is valid, I would appreciate it

Consider the following argument:

  If $0 > 1$ then $1 > 2$.

Proof: Starting with $0 > 1$, add $1$ to both sides.

Since it is not true that $1 > 2$, we can conclude that $0 > 1$ is also false.

The same is true in your example. Starting with some assumption A, you prove property B. However, property B is clearly false, so assumption A must have been false as well. Don't forget that you can derive everything from False.


What progress has been made on persistent catenable deques in the last decade? I'm interested in persistent catenable deques: deques that can be concatenated.

Kaplan and Tarjan came up with the first such data structure in 1995; Okasaki came up with a simpler, amortized version in 1997 using lazy evaluation (see Okasaki for references). Then a couple years later, Kaplan, Okasaki, and Tarjan came up with a simpler implementation using more general mutation in a disciplined manner. Then in 2003, Mihaesau and Tarjan came up with a simpler, non-bootstrapped strictly functional version.

My questions:

The Mihaesau and Tarjan catenable deques appear, to my untrained eye, to offer $O(\log n)$, or possibly even $O(\log(\min(i, n-i)))$ random access (lookup and modify). Is this correct?
Has anyone come up with any simplifications since then?
Has anyone either found a way to combine $O(\log n)$ (or, better yet, $O(\log(\min(i,n-i)))$) splitting along with $O(1)$ concatenation, or proved that it can't be done? For that matter, what about $O(\log n)$ arbitrary insertion and/or deletion?

I don't think the Tarjan and Mihaesau catenable deques have that lookup/modify performance. The non-catenable ones certainly do, though.

I don't think there are any published simplifications since then. As far as I can tell, the T&M version wasn't ever published in a peer-reviewed venue. Publication about purely functional data structures seems to have slowed down in the last few years.
As far as adding splitting while maintaining constant-time concat, you can look at Brodal et al's "Purely Functional Worst Case Constant Time Catenable Sorted Lists" for some references. I don't think this problem is solved yet. As far as I know, the best known result is O(lg lg n) concat and O(lg min(n - i,i)) split, from Kaplan & Tarjan's "Purely functional representations of catenable sorted lists". For the insertion and deletion case that involves lookup, see the lower bounds I mentioned in another question on ropes. For the insertion and deletion case without lookup, you can use an order-maintenance structure.


Showing that Karger's contraction algorithm has exponentially small probability of finding an optimum I'm stuck with one of my homework exercises:

Consider the following variant of Karger’s algorithm for finding a minimum s-t cut, i.e., a minimum cut separating two specific given nodes s and t:
As in the original algorithm, edges are iteratively contracted. In any iteration, let s and t denote the possibly contracted nodes that contain the original nodes s and t, respectively. To ensure that s and t do not get contracted, at each iteration any edges connecting s and t are deleted, and a random edge to contract is selected from the remaining edges.
Give an example showing that the probability that this method finds a minimum s-t cut can be exponentially small.

I know how Karger's algorithm works, but I'm not sure why the probability is exponentially small and how can I show that by giving an example.
Any hint would be helpful.

Consider a graph $G$ with nodes $s$ and $t$, and $n-2$ other nodes $v_1, ..., v_{n-2}$. There are two parallel edges from $s$ to $v_i$, and one edge from $v_i$ to $t$. The minimum $s-t$ cut is to separate $t$ by itself.

If we run the version of the contraction algorithm described in the problem, it will independently contract each of the length-2 paths from $s$ to $t$ in some order. In order for it to find the minimum $s-t$ cut, it must contract $v_i$ into $s$, not into $t$. There is a $\frac{2}{3}$ chance of this happening for each $i$, so the probability that the minimum $s-t$ cut is found is $(\frac{2}{3})^{n-2}$, an exponentially small quantity.

Though, I don't know whether this one works.


Optimized algorithm to compare templates of two websites My task is to compare templates of two websites. I am ready with my algorithm. But it takes too much time to give a final answer.
Here, "template" means the way any page presents its contents.

Example:

Any shopping website have page of any Shoes, that contains,

Images in the left.
Price and Size in the right.
Reviews in the bottom.

If two websites are of any specific product, then it returns "Both are from same templates". Example, this link and this link have the same template.

If one website shows any product and another website shows any category, then it shows "No match".
Example, this link and this link are from different template.

I think that this algorithm requires some optimization, that's why I am posting this question in this forum.

My algorithm

Fetch, parse two input URLS and make their DOM trees.
Then if any page contains , UL and TABLE , then remove that tag. I done this because, may be two pages contains different number of items.
Then, I count number of tags in both URLS. say, initial_tag1, initial_tag2.
Then, I start removing tags that have same position on corresponding pages and same Id and their below subtree, if that tree has number of nodes less than 10.
Then, I start removing tags that have same position on coresponding pages and same Class name and their below subtree, if that tree has number of nodes less than 10..
Then, I start removing tags that have no Id ,and No Class name and their below subtree, if that tree has number of nodes less than 10.
Steps 4, 5, 6 have (N*N) complexity. Here, N, is number of tags. [In this way, in every step DOM tree going to shrink]
When it comes out from this recursion, then I check final_tag1 and final_tag2.
If final_tag1 and final_tag2 is less than initial_tag1*(0.2) and initial_tag2*(0.2) then I can say that Two URL matched, otherwise not.

I wrote my code in Java using Jsoup and Selenium. I asked before on Stack Overflow, but the answers did not help me.

I think a lot about this algorithm, and I found that removing node from DOM tree is pretty slow process. This may be the culprit for slowing this algorithm.

I discussed with some geeks, and

  they said that use a score for every tag instead of removing them, and add them , and
  at the end return (score I Got)/(accumulatedPoints) or something similar, and on the
  basis of that you decide two websites are either similar or not.

But I didn't understand this. So can you explain this statement, or can you give any other algorithm that solves this problem efficiently?

Reading between the lines, here is what I propose. I assume that you are interested in the structure of websites, so the first step is to expose this structure.

Throw away all non-structure tags as well as attributes (maybe keep class) and text.
 I imagine we would be left with <div>, <table>, <ul>/<ol>¹, HTML5 structure tags and little else, depending on coding style.
 For the sake of efficiency, use a SAX-style parser for this step.
Create a tree of the remaining tags, either directly or in a second run.
 The structure of this tree should hold the information you want.
 You may want to cut everything that is nested deeper than some level;
 the overall structure of some website is likely to be clear from the first
 five to ten levels.
Compare the trees. What is useful here depends heavily on the kind of
 similarity you want and on the degree of sophistication the used websites
 display.

Equality of trees would be simplest measure but also coarse. There
 has been work on tree similarity measures, see e.g. here. Some research may unearth a measure that suits your purpose.

Finetuning the steps will require experiments and will most likely depend on the class of websites you compare.

You say you remove lists and tables because the may contain different numbers of elements. While that is true, the action is overcompensating since the occurrence of a list or table can be significant. Instead, remove all contained tags but keep the main ones. But then again, maybe the templates differ in the amount of columns in some table?


Increased rounding relative error when subtracting I'm reading the book "Lessons in Scientific Computing" by Schoerghofer and it says:

  If x and y are real numbers of the same sign,
  their sum x + y has an absolute error that adds the two individual absolute
  errors, and the relative error is at most as large as the relative error of x or y. Hence, adding them is insensitive to roundoff. On the other hand, x−y has increased relative error.

I am not sure how to obtain the result for subtraction, i.e. how to show for
$$
x(1+\epsilon_x)-y(1+\epsilon_y) = (x-y)(1+\epsilon)
$$
that $\epsilon\ge\max(\epsilon_x,\epsilon_y)$.

On the other hand, $x−y$ has increased relative error.

The correct conclusion should be $x-y$ may have increased relative error. In other words, $x-y$ may have decreased relative error.

Let us review what is absolute error and relative error in scientific computing.

The absolute error in approximating $x$ by $\hat x$ is $e = e_x= e_{x, \hat x}= \hat x − x$. The relative error is $\epsilon =\epsilon_x=\epsilon_{x,\hat x}=\dfrac ex$, a dimensionless measure of error which is usually considered more informative.

Yuval has shown an extreme example where the relative error becomes 0. Here are a few more examples on the relative error of approximating $d=x-y$ by $\hat d =\hat x-\hat y$.

$x=2$, $\hat x=2.04$, $y=1$, $\hat y = 1.03$. Then $\epsilon_x = 0.02$, $\epsilon_y=0.03$, $d=1$, $\hat d=1.01$, $\epsilon_d=0.01$.
$x=4$, $\hat x=4.04$, $y=1$, $\hat y = 0.95$. Then $\epsilon_x =0.01$, $\epsilon_y=0.05$,  $d=3$, $\hat d=3.09$, $\epsilon_d=-0.03$.
$x=21$, $\hat x=21.4$, $y=20$, $\hat y = 20.2$. Then $\epsilon_x \approx 0.019$, $\epsilon_y=0.01$,  $d=1$, $\hat d=1.2$, $\epsilon_d=0.2$.
$x=2100$, $\hat x=2140$, $y=2098$, $\hat y = 2096$. Then $\epsilon_x \approx 0.019$, $\epsilon_y\approx0.00095$,  $d=2$, $\hat d=44$, $\epsilon_d=22$.

We can make several observations.

The example 1 shows the relative error of the difference can be smaller than both original relative errors while example 2, 3 and 4 demonstrate the absolute value of the relative error can be bigger than one or both of the original relative errors. In particular, the example 4, where $\epsilon_d = 2310\max(\epsilon_x, \epsilon_y)$ illustrates the relative-error explosion where the relative error can go wildly larger when the two original values, which are 2100 and 2098 here, are near to each other.

Exercise 1. Let $x=cy$ for $x, y>0$. Let $\hat x=x(1+\epsilon_x)$, $\hat y = y(1+\epsilon_y)$. Let $d=x+y$ and $\hat d=\hat x+\hat y$. Then $$|\epsilon_d|\le\max(|\epsilon_x|,|\epsilon_y|)$$

Exercise 2. Let $x=cy$ for $x, y>0, c>1$. Let $\hat x=x(1+\epsilon_x)$, $\hat y = y(1+\epsilon_y)$. Let $d=x-y$ and $\hat d=\hat x-\hat y$. Then $$|\epsilon_d|\lt \frac {2c}{c-1}\max(|\epsilon_x|,|\epsilon_y|)$$


Pi approximation with Montecarlo: Why not just evenly distributed points? With the randomised algorithm for Pi approximation (see https://www.geeksforgeeks.org/estimating-value-pi-using-monte-carlo/ ), I keep wondering why just using points with an even distance should'n work just as fine.

Obviously, with the montecarlo method you get a better approximation the more random points you generate. But isn't an algorithm that just uses the 10000 in a 100x100 square just as good?

Let us compare the efficiency of both methods. The first method generates random points on the unit square $[-1,1]^2$, and checks how many of them lie inside the unit circle – the fraction should be $\pi/4$. If we sample $N$ points, our estimate has roughly normal distribution with mean $\pi/4$ and variance $\pi/4(1-\pi/4)/N$, and so we expect an error of order $1/\sqrt{N}$.

The second method generates an $M \times M$ grid inside $[-1,1]^2$ (we can take $M = \sqrt{N}$ for later comparison), and checks how many of the $M^2$ points lie inside the unit circle. If we think of each point as standing in for a grid square, then we can estimate the number of problematic squares (those intersecting the circle) as $\Theta(M)$ out of the $M^2$, leading to an overall error of order $1/M = 1/\sqrt{N}$, just as before.

We can speed up the second method, however: for a given value of $x$, we can use binary search to locate the $y$ coordinates at which the circle crosses the grid. This gives an $O(M\log M)$ algorithm, an almost quadratic speedup over the two algorithms mentioned above. This is very similar to evaluating the integral $2\int_{-1}^1 \sqrt{1-x^2} \, dx$, implementing the square root using a binary search.


Selection of dates respecting delay constraints I encountered an issue at work that can be derived approximatively to this problem.

Let say we have a machine that can be triggered to instantly do an action. There are several (between 10 to 15) possible triggering times per day.

I have to select exactly 5 times per day (between 00:00 a.m. and 12:00 p.m) to respect the following constraints:

a minimum delay between two selections (for instance 2 hours)
a maximum delay between two selections (for instance 10 hours)

The delay between the last selection of the day and the first of the next day also has to be considered for constraints.

I need an algorithm that find one solution or if there is no solution.

Until now, I did not have the constraint on the maximum delay. Thus, I solved it greedily, day after day, picking the soonest possible date until 5 times are selected. At any moment if no times was available for the day, the problem had no solution.

So does this maximum delay constraint make the problem NP-complete ? Or is there a polynomial algorithm that can solve it ?

This can be solved in polynomial time using dynamic programming.

We'll build up an array $A$.  The meaning of the array is as follows: if $t$ is a time on day $d$ and $i \in \{1,2,3,4,5\}$, then $A[t,i]=1$ means that it's possible to build a schedule for days $1..d$ that ends at time $t$ and obeys all the constraints (minimum delay $\ge$ 2 hours, maximum delay $\le$ 10 hours, exactly 5 times chosen on days $1..d-1$ and exactly $i$ times chosen on day $d$).

Note that, once you've filled in $A[1..t-1,1..5]$, you can fill in $A[t,1..5]$ via a simple recurrence relationship: e.g.,

$$A[t,1] = \lor_{t'} A[t',5]$$

where $t'$ ranges over all times that are on the day before $t$, and that fall at least 2 hours before and at most 10 hours before $t$; and

$$A[t,i] = \lor_{t''} A[t'',i-1] \text{ for } i=2,3,4,5$$

where $t''$ ranges over all times that are on the same day as $t$ but before $t$, and that fall at least 2 hours before and at most 10 hours before $t$.

Thus, you can fill in the array $A$ entry-by-entry, in order of increasing $t$.  This will give a linear-time algorithm for finding a valid schedule that meets your constraints.


What is Turing's main argument in "Computing Machinery and Intelligence"? I read Alan Turing's paper "Computing Machinery and Intelligence" a few times and it isn't clear what exactly is he arguing for. He proposes the imitation game, but doesn't form a concrete conclusion.

It seems like the current consensus is that passing the Turing test doesn't signify human-like intelligence or thinking. It is merely a metric that's easy to measure. Human-like intelligence must necessarily pass the Turing test, but the reverse isn't true.

My understanding is that the Turing test is like the digit recognition test in computer vision. It is an useful metric, but getting 100% on the digit recognition doesn't mean that a computer has human-like vision.

Is Turing arguing that it's possible for a machine to pass the Turing test? Isn't it easily conceivable that a machine could contain every possible question and every possible response? In which case, it could simply look up the appropriate response for any given question, without having to "think" at all. This machine would easily pass the Turing test.
Is Turing arguing that passing the Turing test signifies intelligence or thinking? My example above illustrates a machine that could pass the Turing test, but we wouldn't consider it intelligent or thinking.
Is Turing arguing that the passing the Turing test is merely an arbitrary metric that is easily measurable, since intelligence is too hard to measure? In this case, why is he responding to the objections? E.g. he brings up a theological objection, but that's not relevant if the Turing test is merely measuring Turing's arbitrary metric.

As I see it, the paper is not trying to do any of that.  The introduction is explicit: instead of trying to definitely answer the question "Can machines think?", it suggests an alternative question we can ask that can be specified much more precisely.  "Can machines think?" is vague and open to many possible interpretations; in contrast, the paper proposes a question that is less ambiguous.
(Implicitly, the implication is presumably that this shift of perspective might be interesting and help us think more clearly about the topic.  But it's up to each reader to form their own opinion about whether they find this interesting or useful in clarifying their thinking.)
This purpose is explained in clear and direct terms in the essay, particularly in the first paragraph of the essay as well as the second section of the paper.
To answer your specific questions, here is how I read the paper:

No, the paper is not trying to definitively answer the question of whether it is possible for a machine to pass the Turing test. Rather, the paper is suggesting that the question "Can a machine pass the Turing test?" is an interesting question, worthy of our attention.
Think of this like a scientific paper that proposes an experiment -- it's not necessarily trying to persuade anyone about what the result of the experiment will be, but rather suggesting that the experiment would be an interesting one to carry out or to consider.  That can be a useful, even ground-breaking, contribution.

No, the paper is not arguing that passing the Turing test necessarily signifies intelligence or thinking.  As far as I can tell, it doesn't take an explicit position on that.
We could imagine that one position that is compatible with the essay would be to say "I'm not confident I could define exactly what counts as intelligence or thinking -- that seems hard to define -- but whatever the answer is, passing the Turing test seems like it would be a significant milestone."  We could also imagine that another position that seems compatible with the essay would be "Yes, according to the way I personally define intelligence and thinking, passing the Turing test would signify intelligence and thinking."

No, I think it's pretty clear that Turing is not claiming that the metric is purely arbitrary.  On the contrary, the essay tries to argue that investigating this metric is worthy of our time.  See, e.g., section 2, which begins with "The new problem has the advantage of...."  You might find this argument persuasive, or you might not -- you might find the paper's proposal worthy of our time, or you might not -- you might find the paper's proposal arbitrary -- but I don't think it's fair to say that Turing thought the question was arbitrary.

These are my personal opinions and interpretations of the paper.  Others might vary.
Note that I've answered the question "What is the essay arguing?"  I haven't tried to tackle the question "What did Turing think?" since it can be hard to know what someone is thinking, and it's easier to grapple with the intellectual ideas as expressed in a particular paper.
Separately, one might ask "What do many computer scientists think?" or "What views have many computer scientists taken away, after reading the paper and thinking about the subject?" or "How has this paper influenced the perspective of many computer scientists?"  That's a separate question, with different answers, and potentially a bit more subjective.  For instance, you might find that many computer scientists have formed the opinion that the Turing test is possibly the best way we have to formalize the informal question "Can machines think?" into something answerable in a scientific way, and that many computer scientists think that at least in principle it should be possible for machines to think, if we can surmount the engineering challenges (see the Church-Turing hypothesis).
You might also be interested in reading  Human computing power: Can humans decide the halting problem on Turing Machines? and Would creating a complete computer simulation of the human brain prove the Church-Turing thesis? and https://philosophy.stackexchange.com/q/15460.


Dyna-Q in non-deterministic domains I've implemented the Dyna-Q reinforcement learning algorithm and it works perfectly on a discrete deterministic environment, the cliff. However, when applying it to a continuous environment (mountain car) with discretized states (which introduces non-determinism), it fails everytime (using function approximation is not in question here).

My question is: Sutton's description of Dyna-Q explicitly mentions its applicability to deterministic domains. Are there necessary tweaks for it to work in non-deterministic domains?

One approach is outlined in Tucker Balch's Machine Learning for Trading course on Udacity:

Learning T
Learning R

In a nutshell: create a $T_c$ table ("T count") that counts the number of times each subsequent state is reached after taking an action in a given state. Initialize all values to 0.00001 to avoid division by 0 errors. While executing QLearning, observe $s,a,s^\prime$ and increment $T_c[s,a,s^\prime]$.

Formula for calculating the probability of each s' from [s,a]

$$ \frac{T_c[s,a,s^\prime]}{\sum_i T_c[s,a,i]}$$

The numerator is the count of times s,a lead to each s'.
The denominator is the sum of $T_c[s,a,:]$ (normalizes each s' to its probability)

Dyna-Q then updates a state's expected reward as the weighted sum of the reward in each s' weighted by their relative probability.


A tentative satisfiability algorithm General satisfiability (with a few exceptions such as Horn Clauses) is not believed to have an algorithmic solution. However, the following algorithm appears to be a solution for general satisfiability. What exactly is the flaw with the following algorithm?

Let $W$ be an empty set which will contain all variables that necessarily have to be true or false.
Let $L$ be the set of clauses.
Loop through $L$.
Every time a non-conditional variable† is found, remove it from $L$ and insert it into $W$.
If this leaves an empty AND implication‡, remove all variables in that empty implication from $L$ and insert into $W$.
If this leaves an empty OR implication‡, create new instances of the algorithm, where each instance deals with one variable in the implication (i.e. if the implication is: $x V \implies y$, create one instance where $x$ is inserted into $W$, one where $y$ is inserted into $W$ and one where $x$ and $y$ are inserted into $W$).
Set all variables in $W$ to the value they necessarily have to be.
Reinsert the variables in $W$ in $L$ with their changed values and check if all clauses  are satisfied.
If satisfiability is met, then return $L$, else return "Not Satisfiable".

† A non conditional variable is defined as a variable that is necessary true or false, e.g. $\implies x$ or $\implies \neg y$.

‡ An empty implication is defined as an implication where one side is empty (e.g. $\implies x \wedge y$) or the other side is necessarily true (e.g. $\mathrm{true} \vee a \implies b$.

To get a more intuitive understanding of the algorithm consider the following set of clauses $L$:

$$\begin{align}
  a \wedge b &\implies c & \text{(i)} \\
  &\implies f \wedge g & \text{(ii)} \\
  f &\implies \neg a & \text{(iii)} \\
  f \vee a &\implies b & \text{(iv)} \\
  &\implies c & \text{(v)} \\
\end{align}$$

The algorithm will do the following:

1) Since $c$, $f$, $g$ are non-conditional variables, the algorithm will insert them into $W$. $W = \{c, f, g\}$.

2) Removing $c$, $f$ and $g$ will leave the empty clauses: $\implies \neg a, a \wedge b, b$. These will be added to $W$. $W = \{c, f, g, b, \neg a\}$.

3) Reinserting the variables into $L$ will result in the first clauses being violated: $a \wedge b \implies c$. Since $a$ is false, $c$ is false, meaning clause (v) is violated. The algorithm will return "Not Satisfiable"

I am aware that the algorithm appears confusing. Please feel free to ask for clarification.

From comments I now realize that there is no known efficient general satisfiability algorithm. I'm still interested in feedback about my algorithm. Does it work? How does it compare with common algorithms?

Problem 1

The case of $(x\rightarrow y \vee \overline y)$ should be a "non conditional variable" with respect to $x$ (ie. that $\overline x$ should now be inserted into $W$). If this is not true, then your algorithm needs an extra step to infer this. Assuming $(x\rightarrow y \vee \overline y)$ is a "non conditional variable", we continue.

Problem 2

NOTE: this is one problem I noticed; there may very well be other problems.

The problem is with the "empty OR implication" split into two algorithms, is that in its current form, the split does not cover all cases. In particular:

You start with $(x \vee c \rightarrow y)$, then $c$ is removed and we are left with an empty OR implication of $(x \vee [] \rightarrow y)$. You suggest now splitting it into two new problems and solving each of them; one with $x=T\wedge y=T$ and one where $y=T$. But this does not cover all cases. What about the case when $x=F\vee y=F$. However, your algorithm never considers the possibility that $y$ is false.

I think you might be able to fix this by formulating the two new problems as one with $y$ and one with $\overline x$.

Problem 3

What happens when you are left with a bunch of clauses in the form:

$$(a\wedge b \rightarrow c)$$

or

$$(a \rightarrow b \vee c)$$

After reducing everything, these clauses will remain, and you won't be able to test their satisfiability easily.

Analysis

Note: This "O" notation, $\mathcal{O}(something)$ etc., is called Big O notation. $\Omega(something)$ is called Big-omega.

Supposing the algorithm did work in general, it would run in time of $\Omega(2^m)$ worst case, $m$ being the number of variables. The reason is, each splitting of problem into problems of similar size means that the algorithm runs in exponential time. To visualize this concept, look at the following image of a full binary tree (image from here):

Now imagine the original problem is the node on top. We split the problem into two problems on the second level, but they are of similar size (we only get rid of one variable, $x$ or $y$ from the empty OR implication, so we will still have lots of empty OR implications to do each level). We will potentially have to split the problem $\mathcal{O}(m)$ times to get rid of $m$ variables. This means we will have to deal with a tree with $m$ levels. A tree with $m$ levels has $2^m$ leaf nodes (nodes at the bottom). This is called exponential time, and is informally somewhat on-par with all known boolean satisfiability algorithms. But so is brute force: there are $2^m$ possible assignments of the variables, so by brute force you can guess each assignment and check for satisfiability with similar performance!


The communication complexity of Hamming distance mod $4$ If Alice and Bob each have a bit string of length $n$, what is the randomized communication complexity (either one or two-way) of computing the Hamming distance mod $4$?  It seems this is hard to search for online but I am sure it must be well known.

The one-way  deterministic communication complexity is clearly linear as Bob can learn Alice's entire string from the messages she sends him.  He does this by flipping each bit in his string in turn and seeing if the Hamming distance mod $4$ goes up or down (also mod $4$).

If we change the question to ask for the Hamming distance mod $2$ then Alice need only send $1$ bit to Bob. That is the Hamming weight of her string mod $2$.

Consider the following task $f$: Given $x,y \in \{0,1\}^n$, Alice and Bob need to determine whether $d(x,y) \bmod{4} \in \{0,1\}$, where $d(x,y)$ is the Hamming distance between $x$ and $y$.

Let $M_f$ denote the matrix corresponding to this problem: $M_f(x,y) = 1$ if the answer is Yes, and $M_f(x,y) = -1$ if the answer is No. The discrepancy method shows that
$$
R_\epsilon(f) \geq \log \frac{1-2\epsilon}{\lambda_{\max}(M_f)/2^n}.
$$
In our case, you can calculate that $\lambda_{\max}(M_f) = 2^{\lceil n/2 \rceil}$ (I checked this for a few $n$ using Krawtchouk polynomials, but presumably there is a simple proof, since all the eigenvalues are nice). For even $n$, this implies that
$$
R_\epsilon(f) \geq \log \frac{1-2\epsilon}{2^{-n/2}} = \frac{n}{2} + \log(1-2\epsilon).
$$

(When $n$ is odd, the lower bound is slightly worse.)

Exactly the same bound is obtained if we replace the condition $d(x,y) \bmod{4} \in \{0,1\}$ with the condition $d(x,y) \bmod{4} \in \{0,3\}$.


Is ROM primary memory or secondary memory? According to this picture ROM is classified under Main Memory , but isn’t ROM a secondary storage because it’s external and non volatile ?
Any clarification with reference links will be highly appreciated.
Thank you.

The distinction between primary and secondary storage relies on several joint characteristics which the prototypical examples – RAM and hard drives – satisfy:

Primary storage can be accessed directly by the CPU. Access is fast. Data is volatile – it is lost when power is turned off.
Secondary storage cannot be accessed directly by the CPU. Access is slow. Data is non-volatile – it is retained even when power is turned off.
Tertiary storage is similar to secondary storage, but can only be accessed via a network device. Access is even slower.

Where does ROM fall into this classification? The typical usage of ROM in computing (according to Wikipedia, now falling out of use), is for booting. When the computer is started, the CPU is directed to start running from some address, which is memory mapped to read-only memory* containing instructions for booting the system. This kind of memory satisfies the first two properties of primary storage listed above, but not the third property.
(In reality, ROM can be writable – say it is really an EPROM – and sometimes it is really battery-backed RAM.)
Complicating the picture, some I/O devices are memory mapped, and so in this sense can be accessed directly by the CPU. This is (or at least, used to be) common for video. Does video memory count as primary storage or as secondary storage?
What these examples show is that the classification has its limits. The purpose of such classifications is to help us conceptualize how computers work. They shouldn't be taken too seriously – they don't apply in a clean way to all possible situations.


Efficent deterministic algorithm to sort n numbers with many duplicates ( distinct integers $O(\log n)$) I seek to sort a sequence S of n integers with many duplications, such that
the number of distinct integers in S is $O(\log n)$. Give an $O(n \log \log n)$ worst-case time algorithm to sort such sequences.
I tried quick-sort, Merge-sort, selection-sort but not getting the required running time. So the question is to design a deterministic algorithm for the problem described.

It is from the book Algorithm Design Manual by Steven Skiena (2nd Ed) problem no 4-23, page no- 154 with some modification.

How much time does it take to make $\Theta(n)$ queries in a Red-Black Tree with size $O(\log n)$ ?
A detailed solution follows:

Let $T$ be a new empty self-balancing search tree storing pairs of integers, where the order property is w.r.t. the first element of each pair. For each element $A[i]$ of the original array, query $T$ for a node which first element is $A[i]$. If there is no such node, insert a new node $(A[i], 1)$; otherwise, update the node $(A[i], m)$ with $(A[i], m+1)$.
After you are done with all the elements in A, clear $A$ and visit $T$ in-order. For each node $(x, m)$ of $T$, append $m$ copies of $x$ to $A$. Correctness is trivial, and to prove the complexity bound it is sufficient to observe that at any given time the size of $T$ is $O(\log n)$.


Are Turing-recognizable languages closed under intersection? Let $A$ and $B$ be Turing-recognizable languages. Must language $C = A \cap B$ be Turing-recognizable too?

I have a hunch that it should be because we can construct an enumerator for $C$ by enumerating all the languages in $A$ and then all the languages in $B$.

However, I also know that Turing-recognizable languages are not closed under complement, and $\overline{\bar{A} \cup \bar{B}} = A \cap B = C$, which seems to suggest that Turing-recognizable languages are not closed under intersection.

There is clearly a contradiction somewhere in my reasoning. Where is it?

Indeed, the recursively enumerable languages are closed under union and intersection, but not complement. This is not a contradiction: the formula $A \cap B = \overline{\overline{A} \cup \overline{B}}$ tells that a class closed under union and complement is closed under intersection, but does not tell anything otherwise.

A similar example: the set of finite subsets of $\mathbb N$ is clearly closed under union and intersection, but not complement.


How Cellular Automata is related to Automata Theory? I have read about Automata Theory where it is about the study of abstract machines and automata.

And i know that an abstract machine takes the input, process it and create the output, just like Conway's Game of life.

But, what a formal defination can relate it to Cellular Automata, what about Elementary Cellular Automata, can it related also?

There's no particular relationship. "Automaton" just means "machine" and it's unfortunate that we use the term "automata theory" to describe the study of one particular kind of automaton, rather than using a more specific name.  (You can imagine a parallel universe in whcih automotive engineering is called "machine theory" and other mechanical engineers are standing around saying, "We build machines, too!")

Having said that, I assume there's some relationship between cellular automata and automata-theory automata. It's well-known that some automata are Turing complete, in the sense that you can code up a Turing machine as an input to the automaton, set it running and decode what the cellular automaton does as being the operation of the Turing machine. It would not be surprising (to me, as a non-expert in cellular automata) if there are cellular automata that have the same expressive power as regular expressions, i.e., if there are cellular automata that can simulate automata-theory automata but not simulate anything more powerful.


Factorial algorithm more efficient than naive multiplication I know how to code for factorials using both iterative and recursive (e.g. n * factorial(n-1) for e.g.). I read in a textbook (without been given any further explanations) that there is an even more efficient way of coding for factorials by dividing them in half recursively.

I understand why that may be the case. However I wanted to try coding it on my own, and I don't think I know where to start though. A friend suggested I write base cases first. and I was thinking of using arrays so that I can keep track of the numbers... but I really can't see any way out to designing such a code.

What kind of techniques should I be researching?

The best algorithm that is known is to express the factorial as a product of prime powers.  One can quickly determine the primes as well as the right power for each prime using a sieve approach.  Computing each power can be done efficiently using repeated squaring, and then the factors are multiplied together.  This was described by Peter B. Borwein, On the Complexity of Calculating Factorials, Journal of Algorithms 6 376–380, 1985. (PDF)  In short, $n!$ can be computed in $O(n(\log n)^3\log \log n)$ time, compared to the $\Omega(n^2 \log n)$ time required when using the definition.

What the textbook perhaps meant was the divide-and-conquer method.  One can reduce the $n-1$ multiplications by using the regular pattern of the product.

Let $n?$ denote $1 \cdot 3 \cdot 5 \dotsm (2n-1)$ as a convenient notation.
Rearrange the factors of $(2n)! = 1 \cdot 2 \cdot 3 \dotsm (2n)$ as
$$(2n)! = n! \cdot 2^n \cdot 3 \cdot 5 \cdot 7 \dotsm (2n-1).$$
Now suppose $n = 2^k$ for some integer $k>0$.
(This is a useful assumption to avoid complications in the following discussion, and the idea can be extended to general $n$.)
Then $(2^k)! = (2^{k-1})!2^{2^{k-1}}(2^{k-1})?$ and by expanding this recurrence,
$$(2^k)! =  \left(2^{2^{k-1}+2^{k-2}+\dots+2^0}\right) \prod_{i=0}^{k-1} (2^i)? = \left(2^{2^k - 1}\right) \prod_{i=1}^{k-1} (2^i)?.$$
Computing $(2^{k-1})?$ and multiplying the partial products at each stage takes $(k-2) + 2^{k-1} - 2$ multiplications.  This is an improvement of a factor of nearly $2$ from $2^k-2$ multiplications just using the definition.  Some additional operations are required to compute the power of $2$, but in binary arithmetic this can be done cheaply (depending on what precisely is required, it may just require adding a suffix of $2^k-1$ zeroes).

The following Ruby code implements a simplified version of this.  This does not avoid recomputing $n?$ even where it could do so:

def oddprod(l,h)
  p = 1
  ml = (l%2>0) ? l : (l+1)
  mh = (h%2>0) ? h : (h-1)
  while ml <= mh do
    p = p * ml
    ml = ml + 2
  end
  p
end

def fact(k)
  f = 1
  for i in 1..k-1
    f *= oddprod(3, 2 ** (i + 1) - 1)
  end
  2 ** (2 ** k - 1) * f
end

print fact(15)

Even this first-pass code improves on the trivial

f = 1; (1..32768).map{ |i| f *= i }; print f

by about 20% in my testing.

With a bit of work, this can be improved further, also removing the requirement that $n$ be a power of $2$ (see the extensive discussion).


Expected maximum bin load, for balls in bins with equal number of balls and bins Suppose we have $n$ balls and $n$ bins. We put the balls into the bins randomly. If we count the maximum number of balls in any bin, the expected value of this is  $\Theta(\ln n/\ln\ln n)$. How can we derive this fact? Are Chernoff bounds helpful?

The correct approximation here is Poisson. The occupancy of each bin is distributed roughly $P(1)$ (Poisson with expectation $1$), and tail bounds for Poisson random variables show that with probability $1-1/n^2$ (say), the variable is at most $O(\log n/\log\log n)$. A union bound shows that with high probability, all bins contain at most $O(\log n/\log\log n)$ balls.

A good resource on balls and bins is "Balls into Bins" – A Simple and Tight
Analysis by Raab and Steger. They use elementary methods to a range of $m$ (balls) and $n$ (bins) that covers the classical case $m = n$.


An encoding algorithm with an expensive encoder and a cheap decoder I am looking for an encoding algorithm that would have an encoding function with highly expensive computational costs (ideally like scrypt). At the same time its decoding function must be a lot easier to calculate.

Computational costs should not depend on the size of the encoded data. The size of the encoded data can be up to 10 KB. The encoding part of the algorithm should also be small in the sense of not containing a huge constant data set used for calculations. The decoder can be large but not ridiculously (< 10 MB). Some sorts of encryption are not forbidden.

Under computational costs I understand both calculation and memory costs, however one of them would also suffice

Pseudocode:

var encoded = encode("Hello world"); // Takes 10 seconds
var decoded = decode(encoded); // Takes 0.01 second

Encoding by brute-forcing the decode operation should be slower than encoding operation itself unless decode operation can be kept secret.

I was looking at asymmetric cryptography, I may be wrong, but those algorithms usually have equally expensive encryption and decryption functions. And their keys have length of the same order.

Maybe some of NP-complete problems could be a solution, but I don't know how to reuse them.

Thanks!

There is a public-key scheme that achieves this, based on timelock cryptography.  It is parameterized by a parameter $t$, which controls how slow encoding is.  The time to encode (without knowledge of the private key) will be about $O(t)$; the time to decode (with knowledge of the private key) will be about $O(1)$; and the time to generate a private-public keypair (which should probably be counted as part of the running time spent by the decoder) is approximately $O(\lg t)$.  Consequently, by making $t$ sufficiently large, you can have an arbitrarily large ratio between the time to encode and the time to decode.

The specific construction is based on timelock cryptography and the Rabin cryptosystem.  Generate a RSA modulus $n=pq$ that has the following special form: $p=4u-1$, $q=4v-1$, $u \equiv v \pmod 2$, and $\gcd(p-1,q-1)=2$, where $u,v$ are integers.  Let $\alpha$ be the integer such that $\alpha \equiv u \pmod{p-1}$ and $\alpha \equiv v \pmod{q-1}$.  Pick a positive integer $t$, and compute the exponents $e=2^t \bmod \varphi(n)$ and $d = \alpha^t \bmod \varphi(n)$, where $\varphi(n)=(p-1)(q-1)$.  Make $n,t$ public.  The private key is $d$.

To encode a message $x$, you represent your message as a number $x$ that is a perfect square modulo $n$, a la Rabin's cryptosystem.  Then compute $E(x) = x^{2^t} \bmod n$.  This can be computed by repeatedly squaring $x$ (do it $t$ times).

To decode a codeword $y$, you compute $D(y) = y^d \bmod n$.  Given knowledge of the private key, this can be computed efficiently, regardless of the value of $t$.

The person who creates the keypair can compute $d$ efficiently, using $O(\lg t)$ modular squaring operations (compute $\alpha$ using the Chinese remainder theorem, then compute $d$ using fast modular exponentiation, using knowledge of the factorization of $n$).

The parameter $t$ controls the time to encode.  By choosing $t$ sufficiently large,  you can make encoding 10 seconds.  In contrast, decoding takes constant time (you can choose RSA parameters so that you can decode in 0.01 seconds).  Or, to put it another way, creating the keypair takes $O(\lg t)$ time; encoding takes $O(t)$ time; and decoding takes $O(1)$ time.  Therefore, the designer of the scheme can choose how long it takes to encode and how big the gap between encoding vs decoding will be.

This is basically the reverse of a timelock puzzle / timed-release cryptography.  See https://crypto.stackexchange.com/q/606/351, Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify?, and Is it possible to create a "Time Capsule" using encryption?.

Why does this scheme work?  In other words, why does decoding undo the encoding operation?  It works for basically the same reason the Rabin cryptosystem works.  In particular, raising to the $\alpha$th power computes a square root modulo $n$: raising to the $(p+1)/4=u$th power modulo $p$ computes a square root modulo $p$; raising to the $v$th power computes a square root modulo $q$; and by the Chinese remainder theorem, raising to the $\alpha$th power does both simultaneously, thus computes a square root modulo $n$.  Thus $f(x)=x^2 \bmod n$ is a one-way permutation on the set of squares (quadratic residues) modulo $n$, and its inverse is $g(y)=y^\alpha \bmod n$.  The crucial thing is that, without knowledge of the factorization of $n$, there is no known way to speed up repeated application of the function $f$; but with knowledge of $n$, you can dramatically speed up repeated application of the function $g$.  So, encoding involves iteratively applying $f$; decoding uses the trick to apply $g$ many times, but faster than the naive method.


Cache Direct Map (Index, tag, hit/miss) Alright, I thought I understood this concept but now I am confused. I looked up similar problems and their solutions to practice, and that's what threw me off. The question is a homework problem which says:

Below is a list of 32-bit memory address references, given as word addresses.

3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253

a) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with 16 one-word blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

b) For each of these references, identify the binary address, the tag, and the index given a direct-mapped cache with two-word blocks and a total size of 8 blocks. Also list if each reference is a hit or a miss, assuming the cache is initially empty.

(How do I know how many bits the tag and index are supposed to have? Also, it is a miss unless both the tag and the index match, right? Or is it just if the index matches? I'm obviously extremely confused but I really do want to understand!)

My answer for a) :

Memory        Binary          tag          index         hit/miss
3             00000011       0000          0011          miss
180           10110100       0010          0000          miss
43            00101011       0010          0011          miss
2             00000010       0000          0010          miss
191           10111111       1011          1111          miss
88            01011000       0101          1000          miss
190           10111110       1011          1110          miss
14            00001110       0000          1110          miss
181           10101101       1010          1101          miss
44            00101100       0010          1100          miss
186           10111010       1011          1010          miss
253           11111101       1111          1101          miss

b)I'm not sure how to figure this out, but when I looked it up, people were saying the index should be left shifted one bit so that's what I got (I'd like to understand why)

3             00000011       0000          001          miss
180           10110100       0010          000          miss
43            00101011       0010          001          miss
2             00000010       0000          001          hit
191           10111111       1011          111          miss
88            01011000       0101          100          miss
190           10111110       1011          111          hit
14            00001110       0000          111          miss
181           10101101       1010          110          miss
44            00101100       0010          110          miss
186           10111010       1011          101          miss
253           11111101       1111          110          miss

As always, thank you so much for your help.

For a direct mapped cache the general rule is: first figure out the bits of the offset (the right-most bits of the address), then figure out the bits of the index (the next-to right-most address bits), and then the tag is everything left over (on the left side).

One way to think of a direct mapped cache is as a table with rows and columns. The index tells you what row to look at, then you compare the tag for that row, and if it matches, the offset tells you which column to use.  (Note that the order you use the parts: index/tag/offset, is different than the order in which you figure out which bits are which: offset/index/tag.)

So in part (a) The block size is 1 word, so you need 0 offset bits (because $2^0=1$). You have 16 blocks, so you need 4 index bits to give 16 different indices (because $2^4=16$).  That leaves you with the remaining 28 bits for the tag.  You seem to have gotten this mostly right (except for the rows for "180" and "43" where you seem to have missed a few bits, and the row for "181" where you interchanged some bits when converting to binary, I think).  You are correct that everything is a miss.

For part (b) The block size is 2 words, so you need 1 offset bit (because $2^1 = 2$).  You have 8 blocks, so you need 3 index bits to give 8 different row indices (because $2^3=8$).  That leaves you with the remaining 28 bits for the tag.  Again you got it mostly right except for the rows for "180" and "43" and "181".  (Which then will change some of the hits and misses.)


Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following:

There exists a believed-today NP-hard problem called $X$, where its whole input space can be divided into a finite set of groups such that there exists a corresponding "single-threaded" polynomial-time algorithm for each group (that only runs polynomically for the inputs corresponding to its designated group, without any complexity guarantees regarding inputs for other groups).

Since we don't neccesarily have a criteria to know, polynomically, to which group a certain input belongs to, a possible approach to solve such problem $X$ polynomically is to run all algorithms in parallel and wait for the first that finishes, aborting the execution of everyone else.
Since we have at least one polynomial-time algorithm for every possible input of $X$ (because of the conditions given above), and we are executing all algorithms at once, such problem will be solved in polynomial time for every input, and so every believed-today NP-hard problem can be solved polynomically previous transformation to an instance of $X$.
Is there any research in this direction?

$X$ doesn't exist (unless $P = NP$ in general) because your description is self-contradictory. You claim it is NP-hard, yet its input domain can be split in a finite number of disjoint poly-time solvable problems. This makes it $P$.
The idea of executing these algorithms in parallel adds nothing. Even on a single machine you can run N programs 'simultaneously' by distributing computational time in a round-robin fashion, leading to an overhead factor of N to any single program. Set N to be equal to your number of algorithms (which was, by your description, a finite constant), and you end up with a poly-time algorithm.


benchmark data set for Metareasoning problem I am developing algorithm for solving following problem:

Given a set of items with unknown feature(s) (but  know distribution of feature(s)). Algorithm must choose what items to measure(every measure has some cost)). I use Value of information theory to find this measurements.

After measurements are done  algorithm choose K best items from the set, using some utility function that depends on feature values of items.

I crafted few synthetic data sets, but perhaps there are some benchmark data sets that are used for this kind of problems?

Regards.

In this sort of situation, two standard answers are:

Figure out what the practical applications of your algorithm are.  Find a dataset associated with that particular application, and try your algorithm on it and see how well it works.  Measure success using some metric that is appropriate for that particular application.
Look through the research literature to find previously published papers that try to solve the same problem.  Look at what benchmarks they used.  Use the same benchmarks, so that you can compare how well your algorithm does to previously published algorithms.


Number of 1 child nodes in a binary tree Does anybody know how would I approach calculating the maximum number of 1 child nodes (nodes that have exactly 1 child) in a binary tree with n nodes. Please don't give me the actual answer as this is one of the homework problems, I would like to solve it by myself, but I simply don't know where to start. Any help is apreciated.

Try to construct a tree with a lot of 1-child nodes. Start with the root. Let's say the root has exactly one child. Let's say that that child itself has exactly one child, etc.

   So in a tree with $n$ nodes, you can arrange for all but one to have a single child. This means the maximum is at least $n-1$, and of course it's at most $n$. Finally, prove that the maximum isn't $n$: there has to be at least one leaf (0-child node).

I think the maximum over trees of a given depth is a little more interesting. What's the maximum number of 1-child nodes you can cram in a binary tree of depth $n$?

For depth $0$, there's a single leaf, so the maximum is $0$. For depth $1$, enumeration shows that the maximum is $1$. More generally, what tree shape maximizes the number of one-child nodes?


Pancake Sorting Graph Recursive Definition I'm having trouble understanding exactly how the graph for Pn (where n = number of pancakes) is defined recursively for n>= 4. I can see obviously that, in the case of n=4, there will be 4 rough copies of the graph where n=3 with additions of 4 in certain places (where, and how is this defined?). But these copies aren't exact, and I can't find any detail on Wikipedia except for that it is indeed recursively defined. I'm asking with a view possibly to be able to generate a graph algorithmically for n>=4 recursively.

Here is a graph for n=4 (so there are 4! / 24 possible configurations of pancakes, and thus 24 nodes in the graph). Here it is for n=4, on this Wikipedia article: https://en.wikipedia.org/wiki/Pancake_graph.

See this Wikipedia article for more on Pancake Sorting - https://en.wikipedia.org/wiki/Pancake_sorting.

From Wikipedia:

  The pancake graph $P_n$ or $n$-pancake graph is a graph whose vertices
  are the permutations of $n$ symbols from 1 to $n$ and its edges are given
  between permutations transitive by prefix reversals.

$P_n$ can be constructed from $n$ copies of $P_{n-1}$. We can construct $P_4$ from $P_3$, which looks like:

We start by making 4 copies of $P_3$ and numbering them 1 through $n$. Let's look at one particular copy and call it copy $i$. For each node in that instance of $P_{n-1}$, replace $i$ with $n$ and then append $i$ to the end of each sequence. For the $n$th copy, we don't have to do any replacing and can simply append $n$ to the end.

For example, for the 2nd copy of $P_3$ we'll first replace all the 2s with 4s and then append 2 to the end:

We now have a graph with nodes for all of the permutations of the elements from 1 to 4, and we have edges between sequences that can be transformed into one another by flipping a proper prefix. Edges from $P_{n-1}$ are still valid in $P_n$ because the only thing we've done is relabel and append a suffix.

Now go through each node and add a new edge going to the node corresponding to flipping the entire sequence. For example, (4,3,1,2) gets connected to (2,1,3,4), (1,2,3,4) gets connected to (4,3,2,1), etc.

The final graph for $P_4$ as shown in the Wikipedia article linked in the question looks like:


Calculating $\sum_{i=1}^a \lfloor a/i \rfloor i^2$ I have a sum:
$$S = \sum_{i=1}^n{\lfloor a/i \rfloor i^2},$$
where $a$ is a constant.
Is there a way to speed this up? That is, can we avoid iterating overl all $i$s, possibly calculating it in logarithmic or better time, something manageable when $a$ is big, n = a/2? I tried lots with pen and paper, but I cannot see how to do this faster than $O(a)$ time.

The idea is to split the sum into two parts: For individual values of i for $i <= a^{1/2}$, then for individual values of floor (a/i). For example find the smallest and largest values i where floor (a/i) = 1 or 1 <= a/i < 2. The values i^2 can be summed with a simple formula.

Here's how we can do this efficiently:

We have $a/i ≥ k$ iff $i ≤ a/k$ or $i ≤ \lfloor a/k \rfloor$. Define $g(k) = \lfloor a/k \rfloor$, then $a/i ≥ k$ iff $i ≤ g(k)$.

We have $\lfloor a/i \rfloor = k$ iff $a/i ≥ k$ but not $a/i ≥ k + 1$, that is $i ≤ g(k)$ but not $i ≤ g(k+1)$, or $g(k+1) < i ≤ g(k)$.

Define $f(n) = (n \cdot (n+1) \cdot (2n+1))/6$, then the sum of squares from $1^2$ to $n^2$ is $f(n)$. The sum of the squares $i^2$ for $g(k+1) < i ≤ g(k)$ is $f(g(k)-f(g(k+1))$.

So the sum of $\lfloor a/i \rfloor \cdot i^2$ for all i such that $\lfloor a/i \rfloor = k$ is $k \cdot (f(g(k)-f(g(k+1)))$. We pick some m close to $a^{1/2}$. The sum of $\lfloor a/i \rfloor \cdot i^2$ for all i such that $\lfloor a/i \rfloor ≤ m$ equals $k \cdot (f(g(k)-f(g(k+1)))$, summed for 1 ≤ k ≤ m. This covers all $i > g(m+1)$.

To this sum we add $\lfloor a/i \rfloor \cdot i^2 = g(i) \cdot i2$ for 1 ≤ i ≤ g(m+1).


Loop Invariants as Tautologies Would it be correct to characterize loop invariants as a type of tautology?  I ask since the invariant must basically always be true, before the loop starts, before each iteration and after the loop terminates.  I realize that there is the possibility that the invariant could become false during the body of the loop.  But since inside the loop "doesn't count" is it fair to characterize the invariant as a tautology?

A Tautology is a formula (in a certain logic) that is true under every model of that logic. That is, it is equivalent to the formula "$True$".

A loop invariant, however, is a certain claim that is usually true under some models, and false under others (a model in this case is an algorithm). Then, you prove that the invariant is true under your specific model.

If you add axioms to your logic that forces then only model to be the one of your specific program, then indeed this would be a tautology. But such a process (adding axioms and proving that something is a tautology), is what is more commonly known as "proof". (For clarification: even if you add enough axioms, you may not be able to prove your claim, even if it's a tautology, in case of incomplete systems).

For example, consider a loop that increases a variable $i$ by $1$. An invariant of the loop may be that if before the loop $i>0$, then after the loop $i>0$. Indeed, this loop satisfies it. But it is not a tautology, since we can come up with other loops that do not satisfy it.


Can systems that prevent double-spending (e.g. crypto-currencies) be used to attach other unique data? The Bitcoin-solution can be described as "[...] a solution to the double-spending problem using a peer-to-peer network. (official Bitcoin paper, PDF, abstract, first page).

Now I wonder if a similar technology can be used to collect, send and receive other data with the goal to create "unique content". That is data that you either have or you don't have (like a physical object).

A follow-up question is if these objects can be only created by a central instance but once distributed there is no control from this central instance anymore. Like real money: It gets minted but once it is public you don't have to register every cash transaction with the your state.

One application could be a digital trading card game where you either have a "card" or not. You can either trade new cards directly with other humans or you get (buy) new ones from the creator who holds the monopoly over creating and releasing cards.

Did I miss anything in the crypto-currency tech that prevents this scenario?

In theory, yes, a peer-to-peer validation network could be used to enforce any unique content (not just money) assuming a sufficiently large validation network.

"Sufficiently large" is the catch. Bitcoin validates transactions by having the network nodes "vote" on the transaction's validity. According to Satoshi's proposal:

  The system is secure as long as honest nodes collectively control more CPU power than any cooperating group of attacker nodes.

Getting enough honest nodes into your validation network that no amount of compromised or attacker nodes can affect validation would be very hard. You would also probably want these nodes to be controlled by a large number of people. With a large number of nodes and a small number of controllers, it would be easier to compromise significant portions of the network and it would also reduce trust in the network since, despite the number of nodes, the control is still only in the hands of a few. Bitcoin (and all of the other cryptocurrencies that I am familiar with, which admittedly, isn't a lot) accomplished this by incentivizing its validators; Bitcoins are periodically awarded to the "miners" who solve the proof of work problems in the transactions. This also happens to be a convenient way to introduce new Bitcoins.

However, this would be particularly difficult for the digital trading card scenario you mentioned, since that kind of service would likely only appeal to a niche audience. Even if you incentivized by awarding cards, there might not be enough individuals interested in operating validation nodes.

A scheme where a central authority issues the money (or other content) might not fare much better, since, in practice, the central authority would probably either end up controlling or having material influence over a large portion of the network. Remember that the Bitcoin network issues coins, not the Bitcoin devs or any other single person or small group of people.

The take-home is that if you can get enough people to participate in the validation network, then you should be able to defend the uniqueness of any information (money isn't special in this regard). However, getting enough people to participate would probably be incredibly difficult.


How to determine the average of two strings? Given two strings $s$ and $t$, is there a way to find a string $a$ such that $d(a,s)=d(a,t)$, where $d$ is the Levenshtein distance?
I am sure that a genetic algorithm would work pretty well but I would prefer an explicit solution.

Consider the $d(s,t)$ additions, deletions, and edits that transform $s$ in $t$.
Let $*$ be a new character.
Instead of inserting the prescribed character, insert $*$. Instead of deleting a character, change it to $*$. Instead of replacing a character with the prescribed character, replace it with $*$.

As an example, the edit distance between "mars" and "toast" is 4, and the corresponding edits are:

Change "m" in "t"
Add "o"
Leave "a" unchanged
Delete "r"
Leave "s" unchanged
Add "t"

Replace these steps with:

Change "m" in $*$
Add $*$
Leave "a" unchanged
Change "r" in $*$
Leave "s" unchanged
Add $*$

Applying these steps yields "$**$a$*$s$*$".


Type-checking function calls with functional subtyping I'm relatively new to the topic. Suppose that you want to type-check an expression of the form f(a), i.e. a function call. Assuming that all the declarations are provided explicit types, I believe that a simple type-checker would behave as follows:

Given the environment, compute the types of a and f;
Check that the type of f be of the form $T\to U$;
Check that the type of a be a subtype of $T$;
Return $U$ if needed.

But now suppose that, for all $U$, the following subtyping relation holds:
$$
[U]<:\text{Int}\to U
$$
where $[\thinspace\cdot\thinspace]$ denotes the array-type, and that computation (1) finds the types of a and f to be resp. $T$ and $[U]$ for some $T$, $U$. Now, $[U]$ is not a function-type, so check (2) fails. I'm assuming that the definition of $<:$ is completely independent of the type-checker, so we can't just hard-code a check (2.1) for array-types, too. We could instead check that $[U]$ be a subtype of a least acceptable function-type $T\to\top$, where $\top$ denotes the universe-type, but what if function-types are invariant according to $<:$?
I suspect that what I really need is a form of type-inference, rather than type-checking, even though the types of f and a are completely determined, which doesn't make sense to me. What would be the correct approach, here?

Presumably, what Scala does (since you mentioned it) is relax your step 2. It is incorrect to check that the type of $f$ is merely 'of the form' $T → U$ because it is applied. Rather, one should check that the type of $f$ is known to be a subtype of some $T → U$.
In Scala, such subtyping 'facts' can be added by declaration when defining a type. So, arrays are declared to be subtypes of function types. You gave this as:
$$[U] <: \mathsf{Int} → U$$
This is just an axiom that needs to be part of the subtyping check. Scala is actually even more complex than this, but this at least covers the subtyping part.
As Andrej mentioned in the comments, these sorts of arbitrary 'declared' subtyping axioms don't necessarily lead to the nicest behavior (principal types, decidability, etc.). There might be multiple particular strategies that you could replace your steps with to incorporate the change to step 2, and they might have different limitations on what types they can check/infer for various examples.


Transform values of hash functions like MD5 into numbers I have read about the hash function MD5. I found an online calculator which counts the value of MD5 for different data. But the MD5 function returns as result strings like 735b90b4568125ed6c3f678819b6e058, so I can't apply any numerical operation to this value, e.g. mod.

How can I transform values like these into numbers?

The output 735b90b4568125ed6c3f678819b6e058 is just a hexadecimal representation of a 128-bit (in binary) number, which corresponds directly to an integer between $0$ and $2^{128}-1$.  Therefore, you can think of MD5 as returning a numeric value.  You should be able to make the conversion from hexadecimal  string to integer trivially using any programming language (if not, Stack Overflow is the place to go to).


Time complexity to find out the number of ways to parenthesize N matrices I am trying to figure out the $time$ $complexity$ to find out the number of ways we can parenthesize $N$ $matrices$. I have approached this problem as, say if we have $N+1$ matrices then we can parenthesize them in $\dfrac{2N \choose N}{N+1}$ ways

For example, see the below image, here we have 3 matrices which we can represent in a tree and we have 2 nodes which we can arrange to form different unlabeled binary trees in $\dfrac{2N \choose N}{N+1}$ ways which in turn will give us the number of ways in which we can parenthesize these 3 matrices.

But the problem I am facing is that I am unable to figure out the time complexity which this method will take. Any help will be highly appreciated.

These are called Catalan numbers, and the term $\binom{2N}{N}$ is called a central binomial coefficient.

There are several formulas for these numbers which can be used to compute them efficiently, such as the one you present, or

$$C_n = \prod_{k=2}^n \frac{n+k}{k}$$

The problem with writing down the time complexity for computing these numbers is that the Catalan numbers grow exponentially—the number of bits in the output is roughly proportional to the input index. Therefore, the exact time complexity for evaluating these numbers from such a formula is going to depend significantly on the time complexity of your arithmetic operations, especially your choice of multiplication algorithm for large numbers.


What is the relation between word size and size of internal register of a processor? Is there any difference between word size and size of internal register of CPU ,since "Word size" refers to the number of bits processed by a computer's CPU in one go ,so does this imply that word size is architecture dependent and ALU register's size is same as word size ?

The term "word size" is defined in different ways by different sources, but almost everybody agrees that it is architecture dependent.

In the definition you quote: "number of bits processed by a computer's CPU in one go" it is not clear what "processed" refers to.

(Sorry about using ancient example, but I have not really looked at hardware specs for ages)

For example: The 486DX processor can add 32 bit integers for a 32-bit result (plus carry).  It can multiply 32 bit integers for a 64-bit result.  It can add or multiply 80-bit floating-point numbers for 80-bit results.

It has 32-bit integer registers and 80-bit floating-point registers.  The 64-bit int multiplication stores in result in two registers.

I won't even start on the various physical and virtual memory address sizes.

The integer multiply instruction 32x32 -> 64 is an oddity, most integer instructions can only process 32 bits.

Now, what is the word size?

It all depends on your definition.


Relation between the size of sub-problems and number of sub-problems in a recurrence Below is a well-known equation for generalized recurrence relation in a divide and conquer paradigm (as described in CLRS) --

$$T(n) = aT(n/b) + f(n), \quad \text{where} \quad a \gt 1 \text{ , } b \geq 1$$

If we consider a case for merge-sort, the relation will look like this --

$$T(n) = 2T(n/2) + \Theta(n) \qquad \qquad (i)$$

which is quite straight-forward, i.e. we have $2$ sub-problems of size $n/2$ each, ($1/2$ of the original sub-problem), and $\Theta(n)$ operations to merge them.

Now if we have a relation like --

$$T(n) = 3T(n/2) + \Theta(n) \qquad \qquad (ii)$$

then we can assume that there are $3$ "overlapping" sub-problems, as each of them with size $n/2$. Let's consider again --

$$T(n) = 2T(n/4) + \Theta(n) \qquad \qquad (iii)$$

now, what does it mean? Are there $2$ sub-problems with size $n/4$? How is it possible? If we divide the whole problem into $4$ equal sizes then we should need something like $4T(n/4)$ instead of $2T(n/4)$ to balance the recurrence tree (each node with 4 leaves), right? Is this relation realistic?

If this is the case, then why there is no constraint like $b < a$ ? Moreover, is there any algorithm that follows the recurrence as in $(ii)$ and $(iii)$?

A simple, specific example of an algorithm with a type $(iii)$ recurrence is binary search. At each point you decide whether to look in the left or the right half of the current section of the array, so your problem halves, and you only have one subproblem. The recurrence is then $T(n) = T(\frac{n}{2}) + O(1)$.

So you might get a type $(iii)$ any time you "discard" part of the input at each step.

A divide and conquer approach to multiplying large numbers can give you a type $(ii)$ recurrence (obviously there's faster algorithms now though). If you split the numbers in half, you can turn one multiplication of two large numbers in to four multiplications of half-sized numbers, plus some addition. Gauss reduced this to three multiplications of half size numbers (but with more addition and subtraction), so the recurrence for this algorithm is $T(n) = 3T(\frac{n}{2})+O(add)$ (the exact recurrence depends on how you deal with addition/subtraction).


Which addressing modes permits relocation without any change whatsoever in the code? An exercise problem stated that :

Which of the following addressing modes permits relocation without any change whatsoever in the code?

Indirect addressing
Indexed addressing
Base register addressing
PC relative addressing

Somewhere it explained as :

Base register addressing : In this mode , content of base register is added to the address part of the instruction to obtain effective address . A Base register is assumed to hold a base address and the address field of the instruction gives a displacement relative to the base address with a base register , the displacement values of the instruction do not have to change only the value of the base register requires updating to reflect the beginning of a new memory of constant .

Hence , option (3) is true .

I found another explanation too , which stated that base addressing mode and relative addressing mode are suitable for relocation at run time .

My question is :

Which addressing modes permits relocation without any change
 whatsoever in the code?

    Can you explain it in a formal way, please?

Code relocation can be done whenever addresses are not directly specified in the program (absolute), but are relative to some variable or other modifiable source.

In the 2 modes that you correctly specified as able to support relocation of code and data, the effective address is calculated based on the value loaded in another register.

For 3), base addressing, a register points to the base of the structure and the effective address is obtained by computing an offset from the base.  The base address register can be loaded at run time to point to the base of the structure so the code doesn't have to be modified.

For 4), PC relative, the effective memory address is obtained by computing an offset from the current PC.  No matter where the code is loaded in memory, the offsets are always the same so the code needs no modification.

Now the other 2 selections are a little more tricky.
1. Indirect addressing. This supports relocatable code since the effective address is determined based upon the contents of the initial load.  Code and data can move but with a data structure containing pointers to the code and/or data being at a fixed address. For example, the operating system may define that a pointer to the system's CPU database is always located at address 80002000, but the CPU database can be loaded at any address.    You COULD argue that the entire program is not relocatable because the pointers are at fixed locations, but really relocation is the one of the purposes of this addressing mode.

Indexed Addressing.  This depends upon a bit more definition of the term.  If you mean indexed ABSOLUTE mode, then no, I wouldn't consider this to be a mode that supports relocation.  In this case the effective address of data is based on an offset from a literal fixed address (ex: 1000 + R5).  In order to relocate this data (or code) the literal address would have to be changed in the code.  If it's indexed relative to a base register, then yes it supports code relocation since the base register can be loaded at run time.


How to sort an array $A[1..n]$ where all but $\lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$, at $\Theta(n)$ time? Without the unknown $\lfloor \sqrt n \rfloor$ elements this question wouldn't be hard.
After a long time trying to solve the question, the best partial idea I have is to use Radix sort for the $n-\sqrt n$ elements which are in the given range.  Then I would need to sort the $\lfloor \sqrt n \rfloor$ elements in a decent time.
Any help would be much appreciated.

In the rest of the answer I will slightly abuse the notation by treating $A$ as a set. For simplicity I will also assume that the integers to sort are distinct, so that we are dealing with sets instead of multisets. This assumption is easy to remove.
Construct a min-heap $H^-$ and a max-heap $H^+$, each containing all elements in $A$. Extract the minimum  $\lfloor \sqrt{n} \rfloor$ times from $H^-$ and let $S^-$ be the set of the extracted elements.
Similarly, extract the maximum $\lfloor \sqrt{n} \rfloor$ times from $H^+$, and let $S^+$ be the set of the extracted elements. The overall time required so far is $O(n) + O(\sqrt{n} \log n) = O(n)$. (Notice also that $S^- \cap S^+ = \emptyset$ since $2 \lfloor \sqrt{n} \rfloor \le n$ for $n > 1$).
Now you know that all the elements in $A \setminus (S^- \cup S^+)$ are integers between $0$ and $n^{3/2}$ (actually, between $\sqrt{n}$ and $n^{3/2}$, but this is irrelevant), and therefore can be sorted in time $O(n)$ using Radix sort (indeed, each integer in $S \setminus (S^- \cup S^+)$ has just two digits when written in base $n$).
Let $A'$ be the sorted version of $A \setminus (S^- \cup S^+)$.
To obtain a sorted version of $A$, we just need to insert the elements in $S^- \cup S^+$ into the right position of $A'$.
This can be done by first sorting $S^- \cup S^+$ in time $O(n)$ (any quadratic-time algorithm suffices since $|S^- \cup S^+| \le 2 \sqrt{n}$) and then merging the resulting sorted sequence with $A'$ a-la-Mergesort.


Algorithm for Estimating Number of Unique Monthly Visitors Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as simple as just multiplying the number of unique visitors the first week by 4, due to the hotel problem. If 10 people visit your site the first week and the same people are the only visitors to your site the second, third, and fourth week, the total number of monthly unique visitors to your site is only 10.
I know you can use HLL to estimate the number of unique visitors to a site in O(1) space. I'm wondering if there's a similar approach to estimate how many unique visitors there will be after a month, preferably that also works in O(1) space.

After digging into this for a bit, I came across this paper which provides a solution. The paper gives an approach to estimating the number of new species that will be observed given an initial sampling period. It models observing a given species as a Poisson distribution. It gives the following estimator for the number of new species that will be discovered:
$$
\hat{\Psi}(t)=\sum_{k=1}^{k_{m a x}} N_{k} e^{-k}-\sum_{k=1}^{k_{m a x}} N_{k} e^{-k(1+t)}
$$
where $N_{k}$ is the number of species that were observed $k$ times and $t$ is the length of the second sample relative to the initial sample.


Does the empty word count as a 'word'? If I have DFA accepting

$\{w \in \{a,b\}^*$ s.t. on every odd position in $w$ there is a $b\}$

Would the empty word be accepted? Also, would the word $eb$ be accepted?

The empty word belongs to the language, since on all its odd positions -- all zero of them -- we find a $b$.

$eb$ does not belong to $\{a,b\}^*$, hence it does not belong to the language.