Time complexity and upper and lower bounds Consider the following algorithm:
(the print operation prints a single asterisk; the operation x = 2x doubles the value of the variable x).
for k = 1 to n:
   x = k
   while (x < n):
      print ’*’
      x = 2x

Let f (n) be the time complexity of this algorithm (or equivalently the number
of times * is printed). Provide correct bounds for O(f (n)) and Ω(f (n)), ideally
converging on Θ(f (n)).
This question is one of practices in The Algorithm Design Manuel.
I found the time complexity to be $\sum\limits_{k=1}^{n}\lceil\lg(\frac n k)\rceil$
My question is, could this (or any function) be its own upper and lower bound?
Also is there a way to simplify this function (like writing the sums using some formula like $\frac{n(n+1)}2$)?
Thanks in advance.

Ever heard of Stirling's approximation? :) Well, it implies that $(\frac{n}{e})^{n} \leq n! \leq e^2 \cdot (\frac{n}{e})^{n+1}$. We will use it get a nice upper and lower bound on your function:
Upper Bound:
$$\sum_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil \leq n + \log \frac{n^n}{n!} \leq n + \log (e^n)  = O(n)$$
Lower Bound:
$$\sum_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil \geq \log \frac{n^n}{n!} \geq \log \Big(\frac{e^{n-1}}{n} \Big) = \log(e^{n-1}) - \log n= \Omega(n) $$

Thus, we get $\sum_{k = 1}^{n} \Big\lceil \log \frac{n}{k} \Big\rceil = \Theta(n) $


Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$ Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the algorithm / data structure and improve the time complexity to $O(|V|+|E|)$?

If edge weights are integers in $\{0,1,\ldots,K\}$, you can implement Dijkstra's to run in $O(K|V|+|E|)$ time, following @rrenaud's suggestion. Here is a more explicit explanation.

At any time, the (finite) keys in the priority queue are in some range $\{D,D+1,\ldots,D+K\}$, where $D$ is the value of the last key removed from the priority queue. (Every key is at least $D$, because the sequence of keys removed by Dijkstra's algorithm is non-decreasing, and every key is at most $D+K$, because every key has value $d[u] + wt(u,w)$ for some edge $(u,w)$ where $d[u]$ is the distance from the source to some vertex $u$ that has already been removed, so $d[u]\le D$.)

Because of this, you can implement the priority queue with a circular array $A[0..K]$ of size $K+1$, with each cell containing a bucket.  Store each vertex with key $k$ in the bucket in cell $A[h(k)]$ where $h(k)=k \bmod (K+1)$. Keep track of $D$.  Do operations as follows:

delete-min: While $A[h(D)]$ is empty, increment $D$.  Then delete and return a vertex from $A[h(D)]$.
insert with key $k$: Add the vertex to the bucket of $A[h(k)]$.
decrease-key $k$ to $k'$: Move the vertex from $A[h(k)]$ to $A[h(k')]$.

Insert and decrease-key are constant-time operations, so the total time spent in those operations will be $O(|V|+|E|)$.  The total time spent in delete-min will be $O(|V|)$ plus the final value of $D$.  The final value of $D$ is the maximum (finite) distance from the source to any vertex (because a delete-min that takes $i$ iterations increases $D$ by $i$). The maximum distance is at most $K(|V|-1)$ because each path has at most $|V|-1$ edges.  Thus, the total time spent by the algorithm is $O(K|V|+|E|)$.


What is the difference between object detection, semantic segmentation and localization? I've read those words in quite a lot of publications and I would like to have some nice definitions for those terms which make it clear what the difference between object detection vs semantic segmentation vs localization is. It would be nice if you could give sources for your definitions.

I read a lot of papers about, Object Detection, Object Recognition, Object Segmentation, Image Segmentation and Semantic Image Segmentation and here's my conclusions which could be not true:

Object Recognition: In a given image you have to detect all objects (a restricted class of objects depend on your dataset), Localized them with a bounding box and label that bounding box with a label. In below image you will see a simple output of a state of the art object recognition.

Object Detection: it's like Object recognition but in this task you have only two class of object classification which means object bounding boxes and non-object bounding boxes. For example Car detection: you have to Detect all cars in a given image with their bounding boxes.

Object Segmentation: Like object recognition you will recognize all objects in an image but your output should show this object classifying pixels of the image.

Image Segmentation: In image segmentation you will segment regions of the image. your output will not label segments and region of an image that consistent with each other should be in same segment. Extracting super pixels from an image is an example of this task or foreground-background segmentation.

Semantic Segmentation: In semantic segmentation you have to label each pixel with a class of objects (Car, Person, Dog, ...) and non-objects (Water, Sky, Road, ...). I other words in Semantic Segmentation you will label each region of image.


What will be the time complexity of this function (C++) and why? The function:

double sum1(std::vector& v)
{
    if (v.empty()) {
        return 0.0;
    }
    for(size_t i = 0; i < v.size() - 1; ++i) {
        std::sort(v.begin()+i, v.end());
        v[i+1] += v[i];
    }
    return v.back();
}

There are n-1 sorts each one shorter by 1, so time taken by the function for n elements will be:

T(n) = C*n + n*log(n) + (n-1)*log(n-1) + ... + 2*log(2) + 1*log(1)

How to solve this polynomial? Or I missed something?

How to solve the polynomial: Clearly it's less than n * n * log (n) = O (n^2 log n). And clearly it is more than (n/2) * (n/2) * log (n/2) = O (n^2 log n). So it's n^2 log n.

However, your assumption that the sort is O (n log n) is not justified. Each time except the first you are sorting an array that is already sorted with the exception of the first array element. Many sort implementations will sort that kind of array in O (n), so the total time may be just O (n^2).


Puzzle/game of NP class for a high school student Is there any puzzle or game which cannot be decided in polynomial time and whose problem description can be easily understood by a kid? If it is a fun puzzle so much the better.

I want to demonstrate to a high school student the difference between P and NP class of problems using an example. Also, if there's some simple algorithm to show that it can be decided in polynomial time by a non-deterministic machine that would be a great bonus.

There is a list of a bunch of games that are NP-hard here: https://www.ics.uci.edu/~eppstein/cgt/hard.html  You might also enjoy this list of Nintendo games that are NP-hard: https://jeremykun.com/2012/03/22/nintendo-np-hard/.

Some well-known games that can be proven to be NP-hard (in some form or other) include Tetris, Minesweeper, Checkers, Chess, Dots and boxes.

I think Dots and Boxes might be a particularly surprising and accessible one -- it's rather mind-blowing that such a simple-seeming game hides such complexity.

Caveat: do understand that in many of these cases, we're actually considering a variant of the game.  Many games are finite, so there are only finitely many positions, and thus can't literally be NP-complete -- so instead we consider variants.  For instance, instead of chess on a 8x8 board we consider a variant with a $n \times n$ board, or something like that.  The general point still applies but there are technical details that you should make sure you understand before using this in a classroom.


Find the smallest element greater than current element my question is that given a list of integers (lets say A), for each element A[i], find the smallest element A[j] which could satisfy A[i] < A[j] and i < j. Return -1 if there is no such element.

For example, given [4,2,1,9,3], return [9,3,3,-1,-1]

I have come up with a brute force solution which costs $O(n^2)$, but I'm wondering if there could be a more efficient solution.

A better solution would be using a balanced binary search tree.
You can process the elements from the right to left and for each element you find the vertex in the tree with the smallest key greater than this element (a search query on the tree suffice) and then you add the element to the tree.
Total complexity is $O(n\log(n))$ since we are iterating over the elements once and having one query and one insert operations in each iteration.


Minimum amount of swaps needed to sort a stack Given a stack, what is the minimum amount of swaps needed to sort it?
Since the bottom of it stays intact and we slowly move to the upper part of it, if the stack contains n elements, the amount of swaps f(n) would be

  f(n) < n

for n = 1, 2, 3, 4, is that correct? I cannot find a more accurate way to express it.
Also, how do we calculate the f(n) for n > 4?

Your problem is known as Pancake sorting and it is not true that $f(n) < n$. The minimum number of swaps is between $\frac{15n}{14}$ and $\frac{18n}{11}$.

Currently we know empirically that $P_{17} = 19$, which is the Pancake number, giving lower bound of 19 flips in the stack of 17 elements.

The sequence is known as AA058986.


Selecting a subtree in an array representation of a binary tree Consider a zero-indexed array representation of a binary tree (as in a binary heap), where

0 is the root
The left child of i is L(i) = 2*i+1.
The right child of i is R(i) = 2*i+2.

Is there a simple predicate S such that S(i,j) means j is in the subtree rooted at i? It should preferably be quickly computable with something like numpy.

For example, A092754 is the set of nodes in the left subtree of the root 0.

If you change the layout to following:

1 is the root
The left child of i is L(i) = 2*i.
The right child of i is R(i) = 2*i+1.

then formula is simple: binary index of the node is prefix of binary index of any its descendant, f.e. node with index 0b101 is ancestor of any node with index 0b101...

In order to check this property, you need to find index of highest set bit in both numbers hsbit(x) and perform the check descendant >> (hsbit(descendant) - hsbit(ancestor)) == ancestor.

Moreover, it seems that your layout is just the same as mine, but with all indexes decremented by 1.


Proving a string is random I am reading Kolmogorov Complexity by Li and Vitányi:

"Let $x$ be a finite binary string. We write '$x$ is random' if the shortest binary description of $x$ with respect to the optimal specification method $D_0$ has length at least $x$."
By length $x$ I understand the natural number that the binary string maps to canonically.

[proof which I do not understand follows]

"This shows that although most strings are random, it is impossible to effectively prove them random."

However, I am able to produce a counterexample and can find a proof that $x$ is random effectively (there is an algorithm). Iterate over all the words of size up to $x-1$ of a description language. If you find a description $\alpha_x$ such that $D_0(\alpha_x)=x$ ($\alpha_x$ describes $x$) then terminate with verdict that $x$ is not random. If you exhaust all the words of length $<x$(there are finitely many since $x$ is finite so the program halts) and none of them describes $x$ and then terminate with result that $x$ is random.

What is wrong in my counterexample?

The catch is that $D_0$ is only a partial recursive function and it may not be possible to verify that $D_0(\alpha) = x$ in finite time. There is no way around that because $D_0$ must be universal, and there is no way a machine implementing it would halt on every input, because not every Turing machine halts on every input.


Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language? (Pre-note: I'm learning Theory of Computation on my own, so bear with me if I'm saying something wrong/stupid.)

  Why is $L := \{b^2a^nb^ma^3\mid m,n \geq 0\}$ a regular language?

This question appeared in a problem set, whose answer is the following:

  The language is regular. Indeed, it can be expressed by the regular expression $\mathcal{R} := b^2a^*b^*a^3$.

However, I (think I) can find a contradiction using the pumping lemma.

Consider $s = xyz = b^2 a^{p-3}b^1a^3$. (I assume one can take a specific string from the language.)

Clearly, $\forall p>3, s \in L$, and $|s|\geq p$, the pumping length.

Take $x = b^2$, $y=a^{p-3}b^1$, $z = a^3$. (I assume one can take specific values for $x, y, z$).

The pumping lemma says that if $L$ is regular, there is a number $p$ (pumping length) where, if $s \in L \wedge |s| \geq p$, $s$ may be split into three pieces, $s = xyz$, satisfying the conditions:

$|y| > 0$,
$|xy| \leq p$,
$\forall i \geq 0, xy^iz \in L$.

Conditions (1) and (2) are fulfilled.
As for condition (3) ...

$xy^iz = b^2(a^{p-3}b^1)^ia^3$

For $i=0$, $xy^0z = b^2a^3 \in L$.

However, for $i = 2$, $xy^2z = b^2(a^{p-3}b)(a^{p-3}b)a^3$, and taking $p=4$, it is clear that $xy^2z = b^2ababa^3 \notin L$.

Thus, we find a contradiction (because $xy^2z \notin L$) and $L$ is not regular.

(Could you help understand where is the fallacy here?)

The pumping lemma says that there is some $p$ such that every string longer than $p$ can be split in some way that can be pumped.

You've shown that there's some $p$ and some splitting that doesn't work but (since the language is regular), that just means you chose the wrong $p$ and/or the wrong splitting of your string.

In fact, the value of $p$ is the number of states in the smallest automaton that accepts the language (plus one, I think). The language you give is going to need about eight or nine states, so your $p$ was too small. However, that doesn't much matter. Given the string $b^2a^{p-3}ba^3$, we can split it as $x=b^2$, $y=a$, $z= [\text{the rest}]$ and now $xy^iz\in L$ for all $i\geq 0$, as the pumping lemma claims.  Sure, some other splits don't work, but that one does and the lemma just claims that some split works.

Remember: to show that a language is non-regular using the pumping lemma, you need to show that, for every $p$, there is at least one word of length at least $p$ in the language such that every valid splitting as $xyz$ results in $xy^iz\notin L$ for at least one $i$.


Regular expression for a string not containing a set of substrings I'm trying to figure out how to build a regular expression for a language that doesn't contain strings that contain $101$ or $001$. The alphabet is defined as $\{0, 1\}$. I'm stuck on trying to figure out the DFA. Any help would be appreciated.

Hint. Let $A = \{0,1\}$. A regular expression for the complement of your language $L$ is $A^*(101 + 001)A^* = A^*A01A^*$. Now, as Shaull reminded you, $L$ and its complement have the same minimal complete DFA, up to the final states. It is actually relatively small.

If you prefer, you could also take a purely combinatorial approach. Observe that the strings you want to avoid are $101$ and $001$. It means that if a word $u$ of $L$ contains the pattern $01$, then $01$ has to be a prefix of $u$. Now find a regular expression for the set of words not containing the pattern $01$ and from there you should be able to find a regular expression for $L$.


Vorticity Matrix for Markov chain I have a markov chain with $Q(u,v)$ as transition probability matrix and $\pi(u)$ as stationary distribution defined on state space $\Omega$. The dimension of matrix $Q$ is $nxn$ and vector $\pi$ is $1xn$.

I need to construct a vorticity matrix $\Gamma (u,v)$ of dimension $nxn$ which has below properties

$\Gamma$ is skew symmetric matrix i.e, $$\Gamma (u,v) = -\Gamma (v,u) \quad ,\forall \, u,v \in \Omega $$
Row sum of $\Gamma$ is zero for every row i.e, $$ \sum_v \Gamma (u,v) = 0 \quad ,\forall \, u \in \Omega $$
Third property is, $$\Gamma(u,v) > -\pi (v)Q(v,u) \quad ,\forall \, u,v \in \Omega  $$

My question is : How to construct vorticity matrix $\Gamma (u,v)$ which satisfies above three properties? I need to construct at least one such matrix.

Is there any systematic way to build such matrices

NOTE: Transition probability matrix  $P$, and stationary distribution $\pi$ has below properties

Row sum of $P$ is one for each row,
 $$\sum_v P(u,v)=1 \quad ,\forall \, u \in \Omega$$
$\pi$ is probability distribution hence,
 $$\sum_v \pi(v) = 1$$
Stationary distribution condition for $\pi$,
 $$\sum_u \pi(u) P(u,v)  = \pi(v) \quad ,\forall \, v \in \Omega $$

One can verify that the following matrix $\Gamma$ has the desired properties:
$\Gamma = [\pi]Q - Q^{\top}[\pi]$,
where $[\pi]$ is a diagonal matrix with diagonal elements being the stationary distribution. This construction relates closely to the reversibility of a Markov chain as far as I know.


Rearrange pixels to maximize visually distinguishable pattern I have a dataset full of 0s and 1s, and when I visualize it with t-SNE, which does dimensionality reduction. There is clearly some structure in it as shown below. Each color corresponds to a particular category. There are 10 categories, and there are roughly 180 data points for each category. Each data point is a 64-dimension vector, i.e. there are 64 features. The category information is NOT used by t-SNE, and the coloring is applied after t-SNE run is done.

Since the dataset is all 0s and 1s, and each data point is a 64 vector, so I thought I could plot them as 8x8 dimension binary images as shown below. I have plotted 3 examples for each category

If you compare among images in a single column, there appear to be some similarity sort of. If you compare among images in a single row, they look random to me. My question is that is there such an algorithm for rearranging the pixels, which is equivalent to reordering the elements in the original 64-dimension vector, so that  MAXimize the visual similarity among images in each column (i.e. make them look as similar as possible) while MINimizing the visual similarity among images in each row (i.e. make them look as different as possible)? The whole point to make it easy to spot visual patterns for different categories if possible.

Update:

Thank you for @aelguindy's answer. For the record, I posted what the images look like before scrambling.

This notebook shows how the scrambled version is generated. This dataset is only for experiment. I have another real dataset of 0s and 1s that have nothing to do with hand-written images, of which I was trying to find visual patterns if possible.

This will not be an algorithm in the usual sense. It's a bunch of heuristics that you may find useful. The main difficulty comes from the undefined nature of the phrase "visually similar".

If I understand your question correctly. You have a few separate problems:

Defining what pairwise "visual similarity" is

You are looking for a function $S$ of two vectors to the interval $[0, 1]$. I imagine that you want it to ideally satisfy the following:

$S(\vec{x}, \vec{x}) = 1$, which means that a vector is most visually similar to itself.
$S(\vec{x}, \vec{y}) = S(\vec{y}, \vec{x})$, which means that measuring similarity between $x, y$ does not depend on their order.
$S(\vec{1}, \vec{0}) = 0$, which means that the most unsimilar vectors are the all-ones-vector and all-zeroes-vector.

Even with these restrictions you have a lot of choices. You can just count the number of matching pixels, but a one pixel shift in the image could give you maximum mismatch even if the images are visually very similar.

One simple heuristic that may suffice is counting all matching pixels. Then adding the number of $2\times2$ squares having a matching number of ones (sliding the comparison over all possible sub-squares), ..etc. You can try giving less weight to bigger squares. If you normalize by the maximum value you get (which is computed by comparing an image to itself). You get a value from 0 to 1. It's clear that this satisfies the assumptions above and captures similarity better than just comparing pixels.

These ideas are just examples of what you can do. If you experiment a bit, you can find some interesting $S$'s that capture your personal notion of visual similarity.

Deciding what you want to maximize for the data set.

Now assuming you have such an $S$, the question becomes what do you want to optimize. For a column (resp row), you can compute the sum or the median or the minimum (resp maximum). You can try to maximize the average column similarities minus the average row similarities or something of that sort.

Again, for an abstract $S$ that is not perfectly defined, you need to try different options and see what works best. As a guideline, optimizing for median vaguely means you optimize the common case, while allowing for outliers.

Quickly computing a permutation on $[1 \dots 64]$ that maximizes this quantity.

For some choice of $S$ and a choice of optimization criterion, it is extremely unlikely that you will find an efficient algorithm that finds the permutation optimizing that criterion. As you noticed in your question, the number of permutation grows very quickly with the size of the image.

One common heuristic that works quite well and is really easy to code, is local search. The idea is:

// Obj(p) is the criterion to be maximized.
opt = null
for t trials:
  p = random permutation
  for s steps:
    p' = copy p
    randomly swap two (or three) elements of p'
    if Obj(p') > Obj(p): p = p'
  if Obj(p) > Obj(opt): opt = p

This usually works well in practice. You have the knobs s and t that control the running time, you can even run the different trials fully in parallel. Increasing them usually yields better and better results. t controls the number of "starting points" for the search, which s controls the depth of the search. Again, you will need to experiment a bit.

Hope this helps.


Contained optimal combination of inputs I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to select the optimal combination of players with the highest combined score (i.e. a fantasy football formation) within a $50,000 budget, where a lineup must consist of the following formation:

Goalkeeper x1
Defender x2
Midfielder x2
Forward x2
Utility x1 (can be any position apart from GK)

Each player has a single position and a score, they cannot play in any other position. So in our example, say we have 18 goalkeepers, 22 defenders, 32 midfielders and 28 forwards. We need to select 1 GK (from the 18), 2 defenders (from the 22), 2 midfielders (from the 32), 2 forwards (from the 28) and one not already used non-goalkeeper as a "utility" (from the 100 - 18 = 82).

Currently, I am trying to select the optimal lineup using a brute force technique i.e. generate 1,000,000 random combinations of players which fulfills the above formation and select the lineup which has the highest score.

What other algorithms / techniques could I use to improve upon brute force in this computationally expensive environment (i.e. there are trillions of possible combinations)?

It is a well known problem, known as the multidimensional knapsack problem, and it is easily solvable by dynamic programming for the parameter / problem size you are dealing with here. A very similar formulation is discussed, for example, here.


Stacking Boxes in topological order recently i was solving a programming question on uva judge Stacking boxes
link to the problem : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
EXPLANATION PART
 consider a box with n-dimension and there are k different boxes with n dimension each
so the task is simple we have two insert one box into another and we have to find maximum number of boxes which can be inserted one after the another rotation is also allowed around different axis
for example there are 4 box with 2 dimension
5 2
1 1
5 8
3 2
so the boxes 1 can be rotated and can be inserted into 3 and 2 can be inserted into 1 so the maximum is 3
i have a question that why topological ordering works here why not normal sorting works what i did was first i sorted all the edges of one boxes in increasing order and then  sorted all the boxes in increasing order based on their first index and after that i calculated the longest increasing subsequence

Standard sorting algorithms assume a total ordering: given any two elements, the first is either greater than, equal to, or less than the second. (And this relationship has a few other useful properties, like transitivity.)

However, what you have here is only a partial ordering. Given two boxes, the first might fit into the second, or the second might fit into the first, or they might be the same size…or, neither might fit inside the other. (10, 1) and (2, 5) fall into this last category.

Standard sorting algorithms will choke on this. But topological sorting only needs a partial ordering, and is also more efficient (running in linear time instead of linearithmic). So it's the right tool for the job here.


Hash function, $h(k) = \lfloor km \rfloor$ is simple uniform for real $k$ independently, uniformly distributed in the range $0 \leq k < 1$ I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following statement:

If the keys are known to be random real numbers $k$ independently and uniformly distributed in the range $0 \leq k < 1$ , the hash function
$$h(k) = \lfloor km \rfloor$$
satisfies the condition of simple uniform hashing.

Now what I can understand that they are probably considering uniform disturbution in the "continuous" sense and not in the discrete sense. Had it been in the discrete sense then suppose for $n$ keys the probabity mass function (p.m.f) shall be constant and equal to $1/n$ and so it shall be equally likely for each key to be used in the hashing there-by yeilding the desired result.
But we seem sort of in trouble if the distribution being referred to is continuous (I feel so because of the line: "uniformly distributed in the range $0 \leq k < 1$")
Let $f(x)$ be the associated probability density function (p.d.f) and from the given information we have $f(x)=1$,(which is quite easily found, integrating $f(x)$ in the range $0$ to $1$ and equating it with $1$ and noting that in uniform distribution the p.d.f is a constant).
Now though the p.d.f is a constant but p.d.f is not the probability. Rather probability at a spectrum point is $0$. Now how to use this result to get to the claim of the authors.
Or am I entirely at fault considering the distribution to be continuous?
(There is an answer here, but it does not go into this detail as the question there is different after all).

$h\in [m]^U$ satisfies the simple uniform hashing assumption if when $x\in U$ is chosen uniformly at random, then $h(x)$ is uniformly distributed over $[m]$, or equivalently $\forall i\in[m]: \Pr\limits_{x\in U}[h(x)=i]=\frac{1}{m}$. In our case we have:
$\Pr[h(x)=i]=\Pr\big[\lfloor mx \rfloor=i\big]=\Pr[i\le mx < i+1]=\frac{i+1}{m}-\frac{i}{m}=\frac{1}{m}$.
We used the fact that if $x$ is uniformly distributed over $[0,1]$ then $\Pr[a\le
x\le b]=b-a$ (the equality holds with all four combinations of $\le$ and $<$).


How does computer memory store the file name? I have this doubt for long time. When i save a notepad file, it takes the memory for the information in the file. let's say, I type 'ABC' in notepad and saved the filename as stack, it shows that the memory consumed 3 bytes for the file but what about the file name " stack" ? Where does it store that particular information in our memory?

You are right, the computer saves the file name somewhere. But not, it isn't kept in a "stack" or in "memory", files are kept on external memory (disk, flashdrive, perhaps even somewhere else "on the cloud"). This memory in turn is organized to give an efficient map from file names (stored in filesystem proper data structures) to file contents (arranged so it is e.g. possible to extend the file, erase it's contents and reclaim the space, ...). When you ask your operating system for the file size, it answers with the user-visible space (as that is what you presumably are interested in). The space used up in management of the above (file name, references to the pieces used by this file, map of free space on the device, directory structure for managing names, ...) is usually not your concern. You can ask for it if you look at "how full is the device", just that the space used for management usually can't really be associated with a particular file, it is used by many files together.
Get some book on operating systems, and look up "file systems". Or check simple examples like the (MS-DOS) FAT filesystem or the Unix file system design (just concentrate on the Version 7 one, with it's simple layout). File systems in current use are very complex beasts, trying to squeeze out performance of humongous, glacially slow, rotating disks or levelling wear on fast SSDs.


Even, Itai & Shamir's limited backtracking algorithm for 2-SAT: is it really linear? I have read in Wikipedia (and other sources) about the limited backtracking algorithm of Even, Itai & Shamir for solving 2-SAT problem in a linear time, but the approach doesn't seem to be linear, there is no demonstration nor algorithm implementation to check it.

Here is the algorithm description from Wikipedia: Even, Itai & Shamir - Limited backtracking.

Has anyone heard about this algorithm? Does anyone have its implementation/demonstration?

PS: I am not searching for an algorithm to solve 2-SAT problem in a linear time since I have read about the Aspvall, Plass & Tarjan approach. I am just interested in the former algorithm.

Below you can find a (non-optimized) python implementation of the algorithm. First, I give some hints explaining why this implementation runs in linear time. These hints assume that you know what is roughly going on, and that you have read the code.

The algorithm runs up to two threads at any given time. Initially only one thread is run. Whenever reaching a decision point (a clause with two unassigned variables), it kills the other thread and "forks" the current thread into two. The current thread is killed if it reaches an unsatisfiable clause, and if both threads are dead then the algorithm returns "unsatisfiable".

The algorithm is careful to maintain the following properties:

The two threads are run in lockstep, each step running in $O(1)$ (apart from forking).
Forking takes time $O(t)$, where $t$ is the number of steps since the last fork (or since the start or the algorithm).
The total running time of all non-killed threads is $O(n+m)$ (where $n$ is the number of variables and $m$ is the number of clauses).

These properties guarantee that the main body of the algorithm runs in time $O(n+m)$. The initialization step also runs in time $O(n+m)$, and so the entire algorithm runs in time $O(n+m)$.

There are two somewhat non-trivial implementation details:

Maintaining the partial assignments for the threads. Each thread needs to maintain a partial assignment. Upon reaching a decision point, this partial assignment needs to be forked. A naive implementation would take $O(n)$ to copy the partial assignment. The implementation below uses a two-tiered strategy to handle this: there is a reference assignment which is common to both threads, and there is a per-thread addition. The implementation also keeps track on which variables were set during each thread, and uses this to maintain this data structure.
Handling the repercussions of an assignment. Whenever a variable is assigned, we need to check on all other clauses containing this variable. This is done by precalculating all clauses containing each variable, and keeping a stack of "clauses to check" for each thread. Since a variable could appear in many clauses, we copy one clause to the stack in each iteration. This forces us to keep a state machine (with two states).

The code below accepts two parameters: n is the number of variables, and clauses is a list of pairs of instances of Literal. For example, to check whether the 2CNF $(x_0 \lor \lnot x_1) \land (\lnot x_0 \lor x_2)$ is satisfiable, run

  EIS(3, [(Literal(0,True),Literal(1,False)), (Literal(0,False),Literal(2,True))])

Here is the complete code:

class Literal:
    def __init__(self, var, value):
        self.var = var
        self.value = value
    def __repr__(self):
        if self.value:
            return '+x%d' % (self.var,)
        else:
            return '-x%d' % (self.var,)

def EIS(n, clauses):
    """
Solve a 2SAT formula 'clauses' on 'n' variables.
The formula is given as a list of pairs of Literal.
Returns a satisfying assignment or None if formula is unsatisfiable."""
    ## construct for each variable a list of clauses it appears in
    clauses_by_variable = [[] for _ in range(n)]
    for index,clause in enumerate(clauses):
        for literal in clause:
            clauses_by_variable[literal.var].append(index)
    ## initialization
    # reference assignment
    reference_assignment = [None for _ in range(n)]
    # thread variables:
    # thread is alive
    thread_live = [True, False]
    # thread is currently updating the stack (either (var,index) or None)
    thread_stack_update = [None, None]
    # new assignment (as partial assignment)
    thread_assignment = [[None for _ in range(n)] for _ in range(2)]
    # variables assigned in this thread
    thread_assigned_variables = [[] for _ in range(2)]
    # next unhandled clause
    thread_next_clause = [0, 0]
    # stack of clauses to handle
    thread_stack = [[], []]
    ## main loop
    while True:
        # check whether any threads are alive
        if all(not thread_live[thread] for thread in range(2)):
            return None
        # advance all live threads
        for thread in range(2):
            if not thread_live[thread]:
                continue
            # check whether thread is updating the stack
            if thread_stack_update[thread] is not None:
                var, index = thread_stack_update[thread]
                if index < len(clauses_by_variable[var]):
                    thread_stack[thread].append(clauses_by_variable[var][index])
                    thread_stack_update[thread] = var, index+1
                else:
                    thread_stack_update[thread] = None
                continue
            # determine next clause to handle
            if len(thread_stack[thread]) > 0:
                next_clause = thread_stack[thread].pop()
            else:
                next_clause = thread_next_clause[thread]
                thread_next_clause[thread] += 1
            # check whether we have finished handling all clauses
            if next_clause == len(clauses):
                assignment = []
                for var in range(n):
                    value = thread_assignment[thread][var]
                    if value is None:
                        value = reference_assignment[var]
                    if value is None:
                        value = True # arbitrary value
                    assignment.append(value)
                return assignment
            # otherwise, read clause and current assignment to variables
            clause = clauses[next_clause]
            ref_values = [reference_assignment[clause[i].var] for i in range(2)]
            thr_values = [thread_assignment[thread][clause[i].var] for i in range(2)]
            curr_values = [ref_values[i] if thr_values[i] is None else thr_values[i] for i in range(2)]
            # check whether current clause is already satisfied
            if any(clause[i].value == curr_values[i] for i in range(2)):
                continue
            # check whether current clause is unsatisfiable
            if all(clause[i].value != curr_values[i] and curr_values[i] is not None for i in range(2)):
                # kill current thread
                thread_live[thread] = False
                continue
            # check whether there is a forced assignment
            if curr_values[0] is not None:
                forced = clause[1]
            elif curr_values[1] is not None:
                forced = clause[0]
            elif clause[0] == clause[1]: # clause contains two identical literals
                forced = clause[0]
            else:
                forced = None
            # handle forced assignment, if any
            if forced is not None:
                thread_assigned_variables[thread].append(forced.var)
                thread_assignment[thread][forced.var] = forced.value
                thread_stack_update[thread] = (forced.var,0)
                continue
            ## we have reached a decision point
            # update reference assignment
            for var in thread_assigned_variables[thread]:
                reference_assignment[var] = thread_assignment[thread][var]
            # undo assignments in threads
            for thr in range(2):
                for var in thread_assigned_variables[thr]:
                    thread_assignment[thr][var] = None
            # initialize threads
            for thr in range(2):
                thread_live[thr] = True
                thread_assigned_variables[thr] = [clause[0].var]
                thread_assignment[thr][clause[0].var] = [False,True][thr]
                thread_stack[thr] = []
                thread_stack_update[thr] = (clause[0].var,0)
                thread_next_clause[thr] = next_clause


Does RAM get an indication of data size required Pre-information:

I'm sure someone has asked something along these lines, but no matter how I word it, I can't seem to find a definitive answer

Question:

Does RAM get some kind of indication as to how much data the CPU requires or is there a set amount of data and if the CPU needs more, it needs to call again (and what is that set amount of data).

During a cache miss, the CPU will require at least a single cache line (32, 64 or 128 bytes). Does the CPU need to query RAM multiple times to get a single cache line (assuming the set amount is 8 bytes) or does the RAM return more data per call or does RAM have some way of being notified as to how much data is required?

I'm aware the CPU is most likely going to call more than just a single cache line to avoid the lengthy request from RAM if more data is needed in future from the same block of memory.

Extra Points:

If you do know and have more information, the following extras would also interest me:

If this is different depending on CPU make (generational differences can also be interesting but if you do add information about that, please skip similar generations)
If this is different depending on RAM type
How the CPU can request a different sized cache line or block size (only applies if RAM returns a fixed size that's the size of a block or cache line)
Any other useful relevant information or resources for further reading

Potential answer:

I seem to have found a clue to the answer when looking at the transfer rate of RAM, specifically where it indicates how to calculate the transfer rate from the specifications and from "DDR SDRAM prefetch architecture" which indicates how many 64 bit "blocks" can be requested per call to RAM (e.g. 8 for DDR3 and DDR4, 4 for DDR2 and 2 for DDR1)

RAM just gets requests for data to move to/from the CPU (really the MMU). Data is moved in units of cache lines.


Reading elements of a countable set with Turing machine I have a basic question about the behavior of a potential Turing machine.

Suppose that $S$ is a countable set of binary strings, so that we can enumerate $S$ as $(s_i)_{n\in \mathbb{N}}$.

Suppose that we want to construct a Turing machine $M$ that, on any input, simply writes each element of $S$ on a tape in order $s_1, s_2, \ldots$. (I realize that $M$ will never halt.)

  But we can construct such an $M$ if and only if our particular bijection
  $\mathbb{N} \to S$ is computable, correct?  Or is knowing that $S$ is countable somehow enough?

By definition, a set $S$ is recursively enumerable if there is a Turing machine that enumerates it.


Notions of information content and randomness of binary square matrix We have well established theory for measuring the information content and randomness of binary strings. Notions such as Shanon entropy and Kolmogorov-complexity were developed for binary strings.

For a binary square matrix, it is not sufficient to just convert the matrix into binary string and measure its information content or its randomness since naive unraveling of the binary matrix into binary string would lose the adjacency information in each row and in each column.

My question: What are the analogous notions for measuring the information content and randomness of binary square matrix?

You claim that unraveling the (square) matrix into a vector loses some information. However, the transformation is bijective - given the $n^2$ vector, you can easily reconstruct the $n\times n$ matrix. Information theory is oblivious to representation. If you have some random variable $X$ and some bijection defined on its domain $f$ then $H(X) = H(f(X))$. So classical information theory covers the case of matrices.


When is a bound asymptotically tight? What does it mean that the bound $2n^2 = O(n^2)$ is asymptotically tight while $2n = O(n^2)$ is not? We use the o-notation to denote an upper bound that is not asymptotically tight.

The deﬁnitions of O-notation and o-notation are similar. The main difference is that in $f(n) = O(g(n))$, the bound $0 \leq f(n) \leq cg(n)$ holds for some constant, $c>0$, but in $f(n) = o(g(n))$, the bound $0 \leq f(n) < cg(n)$ holds for all constants, $c>0$.
So what is the difference in big-O notation and small-o notation?

We say that a bound $f(n) = O(g(n))$ is tight if in fact $f(n) = \Theta(g(n))$, that is, if also $g(n) = O(f(n))$. So $2n^2 = O(n^2)$ is tight since $n^2 = O(2n^2)$, whereas $2n = O(n^2)$ is not tight since $n^2 \neq O(2n)$.

As you mention in your question, if $f(n) = o(g(n))$ then the bound $f(n) = O(g(n))$ is not asymptotically tight. However, there is a third option: it could be that $f(n) = O(g(n))$, $f(n) \neq o(g(n))$, and yet the bound $f(n) = O(g(n))$ is not asymptotically tight. An example is $f(n) = n|\sin n|$ and $g(n) = n$.

One could also define $f(n) = O(g(n))$ to be tight if $f(n) \neq o(g(n))$. In that case the "third option" is that $f(n) = O(g(n))$ is asymptotically tight although $f(n) \neq \Theta(g(n))$.


Proving that a language defined by a regular expression is equivalent to a right linear grammar After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me.
Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the right-linear grammar $G= (\{S,A\},\{0,1\},S,P)$, where $P$ consists of the following rules:

$S\rightarrow 1A|01S|\lambda$
$A\rightarrow 00A|11S$

Prove that $L(G)\subseteq L(r)$ and vice versa.
In general, how exactly do I prove that a regular grammar describes the same language as a regular expression?

Let's try to simplify your grammar. First, notice that $A$ generates $(00)^*11S$, and so we can get rid of $A$, obtaining
$$
S \to 1(00)^*11S \mid 01S \mid \lambda
$$
Similar reasoning shows that your grammar generates the language
$$
(1(00)^*11+01)^* = ((1(00)^*1+0)1)^*,
$$
which is identical to your regular expression.
While the reasoning above is informal, it can be made formal with some work.


Longest path in undirected tree Given an undirected tree (with no specific root), how to find the longest path, i.e. 2 vertices that are the farthest apart from each other? There are no lengths associated with the edges (each edge has length 1 by default).
Obviously one idea is to check the path lengths between all pairs of vertices (e.g. by doing a DFS from each vertex), but there should be a more efficient solution. Please include a short proof in your answer.

I think one solution is to do a single DFS (from any node) to determine the longest path, in "divide and conquer" fashion. Apologies in advance for the clumsiness of the description - I'm not sure what's the proper notation for these things.

First, some background: at each step of the DFS we're exploring a subtree T, with the current vertex R considered to be the root of that subtree. All the neighbors of the root (excluding the "parent" in the DFS sense, which is not part of T) form subtrees T1, T2 ... Tk of T.
At each step, we determine both the longest path in T, let's call it p(T), and the longest root path in T (root path = path starting from R), let's call that rp(T).
To do that, we find the same for each subtree T1, T2 ... Tk, then
rp(T) = R--longest(rp(Ti)), i=1...k (I'm using "--" to symbolize joining the vertex R to the path), and
p(T) = longest(rp(T), longest(p(Ti)), rp(T)--2ndlongest(rp(Ti)))
Some explanation about the last term: it only appears if k>1 (at least 2 subtrees), and it joins the 2 longest root paths in the subtrees, through R.
If k=0, then both p(T) and rp(T) are the 0-length path R.

I think a rigorous proof is not necessary - it is quite obvious that for each subtree T, p(T) is either in one of its subtrees Ti, or starts from R going into a subtree (this is rp(T)), or passes through R, going into 2 subtrees. And all the path parts going into subtrees must be the longest root paths in those subtrees. All the cases are handled.

As far as I can tell, the complexity is O(n) since this is a tree.

Implementation note: for each vertex we can store the lengths of p(T) and rp(T), a flag indicating which of the 3 situations we're in for p(T), references to (up to) 2 neighbors that contain a piece of p(T), and the next neighbor vertex for rp(T). At the end, we can reconstruct the longest path from this information.


DFA accepting strings with at least three occurrences of three consecutive 1's The problem states the following:

  Draw a deterministic finite automaton (DFA) accepting strings containing at least three occurrences of three consecutive 1's on alphabet $\Sigma=\{0,1\}$ with overlapping permitted.

I was able to come up "without overlapping" version as follows:

Regex of this DFA is (1+0)*111(1+0)*111(1+0)*111(1+0)*.
However this DFA does not accept 11111. This string should be accepted as the problem says overlapping of groups of three consecutive 1's is allowed. But I am not able to guess how do I do this. I feel I cannot do it with DFA as this will require to have some form of memory (for example, once I read 111, it should remember first occurrence of three consecutive 1's is read and also two consecutive 1's of next occurrence have already been read) which is not what DFA provides. Am I right with this?

If not with DFA, can I do this with non deterministic finite automaton (NFA) or deterministic pushdown automaton (DPDA) or non deterministic pushdown automaton (NPDA)? Or this can be done only with Turing machine?

No, you don't need NFA (although it is equivalent to DFA) or PDA or Turing machine to solve this problem. It can be easily done with a DFA.

Lets number the states in given DFA in clockwise fashion starting from start state as Q0 to final state as Q9. First of all, it being a DFA, Q9 should have a self loop with label 1 as all possible transitions should be shown from all the states in a DFA.

Now we need to add two states, lets name them Qa and Qb. The changes in the transitions to be made are as follows:-

Instead of having a 1 transition from Q2 to Q3, make a 1 transition from Q2 to Qa.
Instead of having a 1 transition from Q5 to Q6, make a 1 transition from Q5 to Qb.
Make a new 1 transition from Qa to Qb and a 0 transition from Qa to Q3.
Make a new 1 transition from Qb to Q9 and a 0 transition from Qb to Q6.

These changes in the provided DFA will allow it to satisfy given conditions. It simply counts input substring 1111 as two consecutive 111 and skips a step (of three intermediate states), increasing the count be 2.


RSA Encryption Explanation In Khan Academy's RSA Encryption 2 video, I can't understand how they have got from

$$m^e\bmod N\equiv c$$
to
$$c^d\bmod N\equiv m\,.$$

The transcript says,

  01:39 some piece of information that makes it
  01:41 easy to reverse the encryption
  01:44 we need to raise $c$ to some other exponent, say $d$,
  01:48 which will undo the original operation applied to $m$
  01:51 and return the original message $m$.
  01:54 So both operations together, is the same as
  01:57 $m^e$ all raised to the power of $d$,
  02:01 which is the same as $m^{e\times d}$.

The person says if we want to reverse the function to give us $m$ (the encrypted message), we simply have to  raise $d$ to another exponent, $d$, and this reverses it.

Although I know this video isn't supposed to fully explain everything I don't understand how this is done. How can you just raise $c$ to some power and get the original message $m$. Is there some sort of proof or can someone explain it in more detail perhaps? By the way, I pretty much know nothing about encryption/ cryptography. I study CS at college (UK) AND was just watching due to curiousity.

What you have (after generating the keys):

$$ \gcd(p, q) = 1 $$
$$ N = pq $$
and a number $e$ and it's inverse $d$, modulo $\phi(N)$. That is:
$$ ed \equiv 1 \pmod{\phi(N)}$$

Encryption:
$$ c \equiv m^e \pmod{N}$$
Decryption:
$$ m^\prime \equiv c^d \pmod{N} $$
$$ m^\prime \equiv (m^e)^d \equiv m^{ed} \pmod{N} $$

We don't yet if $m^\prime \equiv m$.

Well... you can use Euler's Theorem:
$$ a^{\phi(N)} \equiv 1 \pmod{N}, \text{ if } \gcd(a,N) = 1. $$

Write $ed = 1 + k~\phi(N)$:
$$ m^\prime \equiv m^{1+k\phi(N)} \pmod{N}$$
$$ m^\prime \equiv m\cdot m^{k\phi(N)} \pmod{N}$$
$$ m^\prime \equiv m\cdot \underbrace{m^{k\phi(N)}}_{1} \pmod{N}$$

So $m^\prime \equiv m \pmod{N}$.


Code to count number of leaves of a tree? I've just started learning C. Can anyone tell me whether my code is correct or not, if not what's the correct version? This is code for counting number of leaf nodes. Is this efficient one if this is correct?

void Count_leaf( Tree* head)
    {       static leaf = 0;
            if(head.left==NULL && head.right==NULL)
            leaf++;
            else
            {     Count_leaf(head.left);
                  Count_leaf(head.right);
            }
    }

Using this recursive algorithm is indeed a correct way. But your code is wrong, and it could use some improvements.

First of all, you are using a pointer for head so you should use -> instead of . to access the left and right element.

Then, using a static variable is not the cleanest way to store the result. You could use the recursion and simply return the result, like so:

int Count_leaf(Tree* head)
{
    if(head->left == NULL && head->right == NULL)
        return 1;
    else
        return Count_leaf(head->left) + Count_leaf(head->right);
}

Finally, you should check if the tree is empty before starting any counting. You can add a simple condition at the start of your fonction to do that:

if(head == NULL)
    return 0;

Here is the final program:

int Count_leaf(Tree* head)
{
    if(head == NULL)
        return 0;

    if(head->left == NULL && head->right == NULL)
        return 1;
    else
        return Count_leaf(head->left) + Count_leaf(head->right);
}


Design the grammar for the following Design the grammar for the following:
L = (a^n)w(w^r)(b^n) where n>=0 and w={a,b}

The answer goes something like this

S->ε/ aSb

S->A

A->ε/ aAa / bAb

here is a sample string for the above with proof

aabaabbb

S=>aSb

S=>aaSbb

S=>aaAbb

S=>aabAbbb

S=>aabaAabbb

S=>aabaεabbb

S=>aabaabbb

here above symbol ε is epsilon


If any 3 points are collinear Given a set $S$ of points $p_1,..,p_2$ give the most efficient algorithm for determining if any 3 points of the set are collinear.

The problem is I started with general definition but I cannot continue to actually solving the problem.

What can we say about collinear points in general, 3 points $a,b,c$ are collinear if the distance $d(a,c) = d(a,b)+d(b,c)$ in the case when $b$ is between $a$ and $c$.

The naive approach has $O(n(n-1)(n-2))=O(n^3)$ time complexity.

How to solve this problem, what should be the next step?

One simple way is to fix a point $x$, compute the slope of the line $xy$ and store it in a hash table for every other point $y$. If there is a collision, then we have collinear points involving $x$. This takes $O(n)$ (if we assume hash table operations take $O(1)$). We then do this for every point $x$ in time $O(n^2)$.

Also if you are aware of the point-line duality (please refer to Artium's comment below), this reduces to checking the $n^2$ possible intersections of $n$ lines, but also makes use of hash tables.

Also it is open whether this can be done in sub-quadratic time as this problem is 3-SUM hard, please refer to this answer.


Why is A implies B true if A is false and B is false? It seems to me that the 'implies' in English language does not mean the same thing as the logical operator 'implies', in a similar way how 'OR' word in most cases means 'Exclusive OR' in our everyday language use.

Let's take two examples:

  If today is Monday then tomorrow is Tuesday.

This is true.

But if we say:

  If the sun is green then the grass is green.

This is also considered true. Why? What is the 'logic' in natural English behind this? It blows my mind.

Humans are bad at logic until they have to employ it to figure out human affairs. Think of "if $A$ then $B$" as a kind of promise: "I promise to you that if you do $A$ then I will do $B$". Such a promise says nothing about what I might do if you fail to do $A$. In fact, I might do $B$ anyhow, and that would not make me a liar.

For instance, suppose your mother tells you:

  If you clean up your room I will make pancakes.

And let us say that you did not clean up your room, but when you walked into the kitchen your mom was making pancakes. Ask yourself, whether this makes your mom a liar. It does not! She would be a liar only if you cleaned the room but she refused to make pancakes. There might be other reasons that she decided to make pancakes (perhaps your sister cleaned up her room). Your mom did not tell you "If you do not clean up the room I will not make pancakes," did she?

So, if I say

  "If the sun is green then the grass is green."

that does not make me a liar. The sun is not green (you did not clean up the room), but the grass turned out to be green anyhow (but your mom made pancakes anyhow).


Variants of the 3-SUM problem The 3SUM problem has two variants. In one variant, there is a single array $S$ of integers, and we have to find three different elements $a,b,c \in S$ such that $a+b+c=0$. In another variant, there are are three arrays $X,Y,Z$, and we have to find a number per array $a\in X, b\in Y, c\in Z$ such that $a+b+c=0$. Call the first variant 3SUMx1 and the second one 3SUMx3.

Given an oracle for 3SUMx3, can we solve 3SUMx1 in linear time?

One option that comes to mind is just to create 3 replicates of the input array $S$ and run: 3SUMx3($S,S,S$). However, this may return two copies of the same item. E.g. if $S$ has only two elements, 1 and -2, then the 3SUMx1 problem has no solution, but 3SUMx3($S,S,S$) will return the fake solution $(1,1,-2)$.

I currently have a solution but it is not linear. To explain the solution, consider first the simpler problems 2SUMx1 and 2SUMx2, in which we only look for two numbers $a+b=0$ in either one array or two different arrays. Given an oracle for 2SUMx2, the problem 2SUMx1 can be solved in the following way.

Let $n$ be the number of elements in the input array $S$.

For i = 1 to log(n):
  Partition the array S to two arrays, X and Y, based on bit i of the index. I.e.:
    X contains all elements S[k] where bit i of k is 0;
    Y contains all elements S[k] where bit i of k is 1.
  Run 2SUMx2(X,Y)
  If there is a solution, return it and exit.
If no solution were found for any i, return "no solution".

This algorithm works because, if there are two different items, $a,b\in S$, whose sum is 0, then their index must have at least one bit different, say bit $i$. So, in iteration $i$ they will be in different parts and will be found by 2SUMx2($X$,$Y$). The time complexity is $O(n \log n)$.

This algorithm can be generalized to 3SUM by using trits instead of bits, and checking all possible pairs of them. The time complexity is therefore $O(n \log^2 n)$.

Is there a linear-time algorithm?

Randomized algorithms

If you'll accept a randomized algorithm, yes, it can be done in linear time.  There's a randomized algorithm whose expected running time is $O(n)$, and where the probability that it takes longer than $c \cdot n$ time is exponentially small in $c$.

Here's the idea.  Randomly permute the entries of $S$, then split it into three equal-sized pieces, each of length $n/3$: let $X$ be the first one-third, $Y$ the second one-third, and $Z$ the third one-third.  Now call 3SUMx1(X, Y, Z).  If this finds a solution, you have a solution to the 3SUMx3 problem.  Moreover, I claim that if there is a solution to the 3SUMx3 problem, then with probability at least $6/27$, this procedure finds a solution.  Therefore, the expected number of times you have to repeat it (before finding the first solution) is constant.

The running time of each iteration is $O(n)$, and you do a constant number of iterations (on average), so the total expected running time is $O(n)$.  The probability that you fail to find a solution after $k$ iterations is $(21/27)^k$, which is exponentially small in $k$.

Where does $6/27$ come from?  Suppose there's a solution to the 3SUMx3 problem, say, $S[i]+S[j]+S[k]=0$.  What is the probability that $i,j,k$ all come from different thirds of the array?  This probability is $3!/3^3 = 6/27$.  So, if a solution to the 3SUMx3 problem exists, then each iteration of the above procedure has at least a probability $6/27$ of finding it.

Deterministic algorithms

What about a deterministic algorithm?  I don't have a specific proposal in mind, but I feel like it's plausible that this construction could be derandomized.

For instance, to give you an idea of the sort of thing I'm talking about, suppose we split the array into thirds once (deterministically).  Suppose there exists a solution $S[i]+S[j]+S[k]=0$. Then there are $3^3=27$ cases for which third each $i,j,k$ falls into.  After you remove symmetries, there are only $1+6+3$ cases:

Type A (1 case): All three indices fall in different thirds.
Type B (6 cases): Two of the indices fall into the same third, and the other index falls a different third.
Type C (3 cases): All three indices fall into the same third.

You can test for a type-A solution in $O(n)$ time, with a single invocation of the oracle:  3SUMx1(X, Y, Z).  Also, you can test for a type-C solution by making three recursive calls to the same solution (one on X, one on Y, one on Z).  This leaves only the question of how to test for a type-B solution.  It seems like you might also be able to test for a type-B solution using a similar recursive algorithm, though I haven't tried to work out the detailed case analysis.  It seems not impossible that perhaps some ideas along these lines could lead to a deterministic algorithm -- though I haven't worked out the details and I'm just speculating at this point.


Find a regular grammar that generates words with even number of a's I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$

where $|vu|_a$ is number of $a$ in $vu$.

I came up with these rules:

$\sigma \rightarrow aa\sigma | ab\xi$

$\xi \rightarrow aa\xi | \epsilon$

This generates words in form: $(aa)^iab(aa)^j\epsilon$, but not all words in $L$ look like this.

How do I make sure that $b$s can be put anywhere in between $a$s in $v$ and $u$.

Edit: I think I found a solution.

$\sigma \rightarrow b\sigma$ | $a\alpha$ | $ab\gamma$

$\alpha \rightarrow b\alpha$ | $a\sigma$ | $ab\eta$

$\gamma \rightarrow b\gamma$ | $a\eta$ | $\epsilon$

$\eta \rightarrow b\eta$ | $a\gamma$

"How do I make sure that $b$'s can be put anywhere in between $a$'s in v and u?"
Hint, you may need another non-terminal.

Here is a hint about the higher-level approach to the question although you did not ask for it, since it looks like you are not in the reasonably correct way to move forward. I would also encourage you to go forward with your approach as far as possible, if only to experience and see why it does not work (it may work in the end).

Let us define two simpler languages,
$$E=\{w | w\in \{a,b\}^*, |w|_a = 0(\text{mod } 2)\}$$
and $$O=\{w | w\in \{a,b\}^*, |w|_a = 1(\text{mod } 2)\}.$$

Can you write regular grammar for $E$ and $O$ ? Can you piece together some E's and O's to form $L$?

Once you have done the problem, you might be able to see a general strategy on how to generate regular grammars for these "simple" languages.


Can a public key be used to decrypt a message encrypted by the corresponding private key? From what I have seen about usage of a pair of public and private keys, the public key is used for encrypting a message, and the private key is used for decrypting the encrypted message.

If a message is encrypted by the private key, can it be decrypted by the corresponding public key?

If yes, can you give some examples of when this case is used?

Thanks.

Q: If you pedal backwards on a fish, does it go backwards?
A: ???

A fish is not a bicycle. Similarly, you cannot use a private key to encrypt a message or a public key to decrypt a message. They don't have the right equipment.

With RSA, which is a popular public-key cryptosystem but not the only one, the private key and the public key have the same mathematical properties, so it is possible to use them interchangeably in the algorithms. (They don't have the same security properties, however — the public key is usually easily guessable from the private key.) You can take an RSA encryption algorithm and feed it a private key, or an RSA decryption algorithm and feed it a public key. However, the results are not meaningful according to standard algorithms.

This symmetry between public keys and private keys does not extend to most other public-key cryptosystems. In general, the public key isn't the right type of mathematical object to use for the decryption algorithm, and the private key isn't the right type of mathematical object to use for the encryption algorithm.

This being said, public-key cryptosystems are based on the concept of trapdoor functions. A one-way function is a function that is easy to compute, but whose inverse is hard to compute. A trapdoor function is like a one-way function, but there is a “magic” value that makes the inverse easy to compute.

If you have a trapdoor function, you can use it to make a public-key encryption algorithm: going forward (in the easy direction), the function encrypts; going backward (in the hard direction), the function decrypts. The magic value required to decrypt is the private key.

If you have a trapdoor function, you can also use it to make a digital signature algorithm: going backward (in the hard direction), the function signs; going forward (in the easy direction), the function verifies a signature. Once again, the magic value required to sign is the private key.

Trapdoor functions generally come in families; the data necessary to specify one particular element of the family is the public key.

Even though public-key encryption and digital signatures are based on the same concepts, they are not strictly identical. For example, the RSA trapdoor function is based on the difficulty of undoing a multiplication unless you already know one of the factors. There are two common families of public-key encryption schemes based on RSA, known as PKCS#1 v1.5 and OAEP. There are also two common families of digital signature schemes based on RSA, known as PKCS#1 v1.5 and PSS. The two “PKCS#1 v1.5” are of similar designs, but they are not identical. This answer by Thomas Pornin and this answer by Maarten Bodewes go into some details of the difference between signature/verification and decryption/encryption in the case of RSA.

Beware that some layman presentations of public-key cryptography masquerade digital signature and verification as decryption and encryption, for historical reasons: RSA was popularized first, and the core operation of RSA is symmetric. (The core operation of RSA, known as “textbook RSA”, is one of the steps in an RSA signature/verification/encryption/decryption algorithm, but it does not constitute in itself a signature, verification, encryption or decryption algorithm.) They are symmetric from the 10000-foot view, but they are not symmetric once you go into the details.

See also Reduction from signatures to encryption?, which explains that you can build an encryption scheme from a signature scheme, but only under certain conditions.


Parameterized Dominating Set What is the best algorithm to compute p-dominating set?

The p-dominating set problem is a parameterized version of minimum dominating set in which the problem takes a parameter $k$ also as an input, and the problem is now whether there exist a dominating set of cardinality at most $k$.

I know the problem is W[2]-hard so there is no chance of getting a $f(k) n^c$ running time algorithm unless the parameterized hierarchy collapses.

Well, you can always solve it in XP time by trying all possible $k$-sets. In fact, it was shown by Pătraşcu and Williams [1] that there is no $O(n^{k-\varepsilon})$-time algorithm for $k$-dominating set for any $\varepsilon > 0$, assuming SETH.

This is almost tight as for $k \geq 7$, the problem can be solved in $n^{k+o(1)}$ time (see [1]). As a special case, you can solve 2-dominating set in $O(n^\omega)$ time, where $\omega < 2.376$ using matrix multiplication.

[1] Pătraşcu, Mihai, and Ryan Williams. "On the possibility of faster SAT algorithms." Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. 2010.


Representing non-contiguous memory regions as a standard vector with O(1) access What interesting alternatives are there for constructing an arbitrarily large static array from smaller scattered blocks of fixed-sized non-contiguous blocks of memory?

This is similar to the problem solved by hardware MMU pagetable mappings from virtual memory to physical memory, but in this particular case the scale is different, and it needs to be implemented in software, with virtual memory, and also in userland.

To clarify a bit, I'm using baker's treadmill as my GC, but it only supports fixed sized allocations (the current chunk size is 128 bytes, but I have some slight flexibility in re-defining it). The language I'm implementing requires arbitrary sized vectors with something close to O(1) access/write.

Currently I'm just building a pyramid of chunks, which gives something like log12(n) lookups, but the memory overhead sucks. Are there any interesting hashing solutions for mapping monotone index ranges to pointers?

What about run-time generation of a minimal perfect hash function? It seems they require at minimum 1.44 bits per key. If we bump the allocation block size to 512, we can support vectors with up to 1454080 elements, since we only need to map block numbers and not vector indices.

Edit:

See the paper "Z-rays: divide arrays and conquer speed and flexibility" (http://dl.acm.org/citation.cfm?id=1806596.1806649&coll=DL&dl=GUIDE) for more information regarding optimization of this array format:

These scattered blocks are sometimes called arraylets and are used by other GC algorithms: https://www.ibm.com/developerworks/websphere/techjournal/1108_sciampacone/1108_sciampacone.html

Also related: the Staccato GC: http://researcher.watson.ibm.com/researcher/files/us-groved/rc24504.pdf

A simple approach is to have a one-level lookup table that maps each block of the array to where it is stored.  In other words, for a logical array $A[0\dots n-1]$ containing $n$ bytes, we have a lookup table $T[0\dots \frac{n}{128}-1]$ containing $n/128$ pointers; the bytes $A[128k \dots 128k+127]$ are stored at the physical address $T[k]$.  To look up $A[i]$, we compute $p = T[i \gg 7]$ (where $\gg$ indicates logical right shift), then read the byte at address $p + (i \bmod 128)$.

This does require a single contiguous region large enough to store $n/128$ pointers (e.g., holding $n/32$ or $n/16$ bytes, depending on whether you're on a 32-bit or 64-bit system).  Given that, array operations become fast: you basically have one extra table lookup and indirection.

If you can't even have any contiguous region, not even a smaller one for storing the lookup table, but have to build everything out of 128-byte chunks that can be at arbitrarily-inconvenient locations with arbitrarily-bad fragmentation, then I don't think it's possible to do any better than your solution.

Rather than looking for a better data structure to handle this kind of arbitrarily-bad fragmentation, a cleaner solution is probably to design your memory management system to avoid creating worst-case memory fragmentation in the first place.  One architecture that can help deal with this is a buddy allocator.  The entire memory address space can be divided into 128-bit chunks, but we then impose a binary tree structure on it: the 128-byte chunk at address $256k$ is the sibling/buddy of the 128-byte chunk at address $256k+128$.  Those two chunks, if they're both available, can be coalesced into a (fused) 256-byte chunk.  Each 256-byte chunk has a buddy, and if they're both available, they too can be merged to obtain a 512-byte chunk.  And so on.  This allows you flexibility to deal with small 128-byte chunks when you need them, but also provides a way to build up larger chunks of contiguous memory and try to avoid arbitrarily-bad fragmentation.


What is the difference between Partition and Division? While reading graph theory, I came across different definitions where they use partitions and divisions, I was wondering, are these terms same or different?
Can anyone explain me their difference in Set Theory?
I know this is a simple question but anyone hardly talk about it but they always make here a mistake.

I will explain this with an example :
Consider a set $S$ which contains a collections of sets with a constant k such that:
$$ S = \{ \{S_1\}, \{S_2\}, \{S_3\},\{S_4\},..........\{S_k\} \}$$
In Partition of Set S :
Then we can form the set again by
$ S=S_1\cup S_2\cup S_3\cup S_4...........\cup S_k$
$where\ S_i\cap S_j = \phi$
$and\ i\neq j\ and\ i,j\in \mathcal{N} $
In Division of Set S :
We just have this
$ S=S_1\cup S_2\cup S_3\cup S_4...........\cup S_k$


In two sets, identify set of pairs with maximal sum of connections Given two sets of items

$A = { a_1, .., a_N }, B = { b_1, .., b_M },$

and assuming a connection weight $w{_i}_j \ge 0$ between any possible pair $(a_i, b_j)$ that contains one item of each set, how can I identify the set of pairs $S$ that maximizes the sum of all involved weights: $\sum_{S}w{_i}_j$, under the condition that any $a_i$ and any $b_j$ occurs maximally once in the new set?

Example: With $A = [a_1, a_2], B = [b_1, b_2, b_3]$, and

$w$'s from $a_1$ to $B$: $[5, 2, 1]$

$w$'s from $a_2$ to $B$: $[1, 0.2, 0.4]$

the solution is to use the pairs: $(a_1, b_1), (a_2, b_3)$ which result in the highest possible sum $5.4$, and $b_2$ is left over.

Also, is there a way to approximate the sum e.g. not optimizing further for those $w{_i}_j < threshold$?

I'm sure this problem has a name, but I'm not able to figure it out.

This is the assignment problem.  There are standard algorithms, such as the "Hungarian algorithm".

If you want to only include edges whose weight is below some threshold, delete those edges first before running the algorithm.


How to reformulate my problem as a mixed-integer quadratic problem I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the $s$-dimensional vector $a$ is to be computed to find $x$.

The only assumption that we have is $x=0$ when we project $x$ onto the space spanned by $s$ different rows (that we don’t know their indices) of the matrix $B$ which has $n$ rows. To do this projection we can use $P_s\in \mathbb{R}^{n\times n}$  which is $1$ on the diagonal entries that correspond to the $s$ selected rows of $B$ and $0$ elsewhere. Hence, $P_s x= P_s z + P_s Ba=0 \implies a=-(P_sB)^{-1}P_sz$.

The main issue is that we don’t know the positions of these $s$ rows, so the problem is combinatorial and we need to go through all possible $n\choose s$ projections to find the exact $x$ which corresponds to the least cost $f(x)=\|y-Ax\|_2$ where $\|v\|_2=\big(\sum_iv_i^2\big)^{1/2}$, $y\in \mathbb{R}^{m\times 1}$ and the matrix $A\in \mathbb{R}^{m\times n}$ are given.

So my question is how I can reformulate my problem as a mixed-integer quadratic programming to go through all possible $n\choose s$ submatrices of $B$ formed by the $s$ selected rows and finally find the set of rows which corresponds to the least $f(x)$.

So it sounds like the problem is the following:

  Given $A,B,y,z$, I want to find the vector $a \in \mathbb{R}^n$ that minimizes $||y-Az-ABa||_2$, subject to the constraint that there must exist some matrix $P_s$ with exactly $s$ 1's on its diagonal and 0's everywhere else, satisfying $P_s (z+Ba)=0$.

Mixed-integer QCQP

This can be formulated as a mixed-integer quadratically constrained quadratic programming problem, as follows.

We have $n$ unknowns $a_1,\dots,a_n$, so $a=(a_1,\dots,a_n)$.  Also introduce $n$ integer zero-or-one unknowns $p_1,\dots,p_n$, with the intention that $P_s$ will be the diagonal matrix whose diagonal is $p_1,\dots,p_n$.  Add the cosntraint that $p_1+\dots + p_n=s$, to ensure that exactly $s$ of the entries on the diagonal are $1$.  Note that each entry of $z+Ba$ is a linear expression in the unknowns, so the constraint $P_s (z+Ba)=0$ can be expressed as $n$ quadratic constraints, each of the form $p_i \cdot e_i=0$ where $e_i$ is linear in $a_1,\dots,a_n$.

Now note that each entry of $y-Az-ABa$ is a linear expression of the $n$ unknowns $a_1,\dots,a_n$, so the objective function is a quadratic function of the unknowns.

Unfortunately, mixed-integer QCQP is a pretty challenging form of non-linear programming, so I don't know how well this will work in practice.  You might have to try it out with some solvers.

This is a pretty brain-dead approach.  There may be smarter approaches that are more effective than this, by taking advantage of the structure of your problem.


RTT (Round Trip Time) calculation How do I calculate RTT, do I start to measure the time from the beginning of the segment transmition or from the moment all the segment had been transmitted?

The end time is the moment the sender gets the "ACK".

The round trip time is the time required to go and return, so it must be measured from the start of the transmission to the start of the reception of the response. If you measure from the end of the packet to the end of the ACK, you are subtracting the package length and adding in the length of the acknowledgement's package (the ACK could be piggibacked on any package doing the back trip). This can very well be measured during a stream of data (and it is done so by your neighborhood TCP stack to tune timeouts and so on).


Multivariate polynomials Given a Diophantine equation $p(x_1,x_2,...,x_n)$,

Can I find a reduction from $\text{dioph}(\mathbb{N}) \leq \text{dioph}(\mathbb{N}_e)$?

$\mathbb{N}_e$ is the set of even numbers.

So I have to find a manipulation of $p$ such that I only have even numbers as solution.

How can I do this? Unfortunately I have no Idea.

So I have to find a manipulation of $p$ such that I only have even numbers as solution.

Not so. You have to find a manipulation of $p$ such that if you can find a solution / all the solutions of the manipulated $p'$ in even numbers, then you can find a solution / all the solutions of $p$. That's a very different problem.


How does SARSA handle episode termination When applied to domains that are episodic and have a "final" state but no final action, like a game, how does SARSA update the Q-values?

e.g. A game agent would receive this series:
$$
    s_0,a_0,r_0,s_1,a_1,r_1,.....s_{N-1},a_{N-1},r_{N-1},s_N
$$
Based on the traditional definition, which updates the current Q-value using the *future Q-value, shouldn't it be impossible to apply SARSA, since there's no future action to use when plugging in the $(s_t, a_t, r_t, s_{t+1}, a_{t+1})$ values?

You can think of the terminal state as a loop for every possible action where you receive zero reward. Once you enter the terminal state, not matter what action you choose, you will receive zero reward.


Binary search algorithm - worst-case complexity I tried to calculate the worst case of binary search (not binary search tree). My calculations:
$$T(n) = T(\frac{n}{2}) + 1$$
$$T(n) = T\left(\frac{n}{4}\right) + (1+1) = T\left(\frac{n}{8}\right) + (1+1+1) = ... = T\left(\frac{n}{2^{k}}\right)+(1\cdot k) $$
$$T(n)=T(1) + (1\cdot k) = c_{1} + (1\cdot k) =  c_{1} + log_{2}n = c_{1}+\frac{log(n)}{log(2)} $$
Finally the complexity should be
$$O(log(n)) $$
Is this a good way to prove the worst case complexity of binary search algorithm? Make I mistakes?

That's a way to do it. Sometimes it's easier to go the other way round: What is the size of the largest array where binary search will locate an item or determine it's not there, using k comparisons? And it turns out that the largest array has size $2^k - 1$. And then you reverse this.

Understanding the master method is very useful if you have to pass a test that tests whether you understand the master method. But be prepared to have more practical problem where the only method that works is the "turn on your brain" method. A simple example is the Greatest Common Divisor algorithm.


Finding optimal set for a sum of a product function over a 2D lattice Given a 2D lattice with coordinates $1 \leq x \leq c$ and $1 \leq y \leq d$, we define $f(x, y) = xy$.

We wish to find a boolean function $I(x,y)$ that determines in $O(1)$ time whether or not $(x,y)$ belongs to the set of points $S$ of size $k$ such that the sum $Z(S) = \sum_{(x,y) \in S} f(x,y)$ is smaller or equal to any other set of size $k$. One may use $O(c+d+k)$ time and space to construct $I$.

Is this possible? Is this a known problem (my search turned up nothing)? Can https://en.wikipedia.org/wiki/Divisor_summatory_function and its approximation help us?

Motivation: I work in NLP and am trying to find an optimal way of storing part of a word-word cooccurrence matrix in memory and part on disk. This matrix is very sparse. I'm making the simplifying assumption that the probability of two works co-occurring is proportional to their unigram frequencies. By ranking words in terms of frequency, we get the $c$ and $d$ terms. So the smaller the ranks $c$ and $d$, the more likely they are to co-occur, so this value should be stored in memory. Since there will be billions of lookups, $I$ needs to be fast.

Thanks!

The set $S$ must have the following form: there must exist a threshold $t$ such that:

If $xy < t$, then $(x,y)$ is in $S$.
Some or all of the points $(x,y)$ with $xy=t$ are in $S$.
If $xy > t$, then $(x,y)$ is not in $S$.

Moreover, in the second bullet, it doesn't matter which points with $xy=t$ you put into $S$; all that matters is how many of them you put into $S$.  Finally, notice that the locus of points $(x,y)$ such that $xy=t$ forms a hyperbola.

It follows that one way to parametrize the set is as

$$S = \{(x,y) : xy < t \text{ or } (xy=t \text{ and } x<u)\},$$

for some parameters $t,u$.  It's clear that, given $t,u$, membership can tested in $O(1)$ time, i.e., your oracle will run in $O(1)$ time, as required.

So, we simply need to select suitable values of $t,u$ during the precomputation to construct $I$.  How can we do that?

One easy way is to use binary search.  Notice that it's easy to count the number of lattice points $(x,y)$ such that $xy < t$ in $O(c)$ time: just iterate over $x=1,2,\dots,c$ and count the number of values $y$ such that $xy < t$, i.e., such that $y < t/x$; there are $\lfloor (t-1)/x \rfloor$ of them, so we sum that over $x=1,2,\dots,c$.  Now use binary search on $t$ until you find the largest $t$ such that the number of such points is at most $k$.  This gives you the value of $t$.  It also gives you the number of points $(x,y)$ such that $xy<t$; call that number $k_0$.

Once you know the value of $t$, the next step is to choose a suitable value for $u$.  We'll need to choose $u$ so that there are exactly $k-k_0$ lattice points $(x,y)$ such that $xy=t$ and $x<u$.  Finding $u$ can be done by iterating over $x=1,2,\dots,c$; for each $x$, check whether $y=t/x$ is an integer, keep track of how many lattice points you've found, and stop once you've found $k-k_0$ of them.

In the end, the precomputation requires something like $O(\min(c,d) \log k)$ time and the oracle can be computed in $O(1)$ time.  The precomputation can probably be done even faster through implementation tricks and/or some number theory, but given your problem statement, I'm guessing this might already be good enough.


What is complexity class for #XOR-2-SAT? I know that given problem is in $\mathsf{FP}$: if given formula is satisfiable, then it is only needed to find out how many connected components equality (undirected) graph has. In fact problem is to count the amount of connected components.
However, is it possible to solve it using only log space? Is then the given problem is $\mathsf{FL}$-complete? Or, maybe, this problem is complete somewhere in $\mathsf{AC}$?

The given problem is in $\mathsf {FL}$:

Solve if it is satisfiable. Let the result be number $s$. Can be done in logarithmic space.
Set $t=0$.
Count the number of clauses of form $(a\oplus \overline a)$ where $a$ does not appear in any other clause except clauses identical to that one. For each such clause increase $t$ by $1$.

Step 3 can be performed in log space as follows:
for every i in V:
    flagIndependent = true
    flagAppears = false
    for every j in C:
        if C_j isIdentical(`(x_i xor not(x_i))`):
            flagAppears = true
        elseif C_j contains(`x_i`):
            flagIndependent = false
    t += flagAppears * flagIndependent

Two variables i and j take space $\log(|V|)$ and $\log(|C|)$ respectively. Variables flagIndependent and flagAppears take $1$ bit each. Functions checking clauses also require $O(\log(n))$ space at most. Therefore the total space used is logarithmic.
The answer is $s2^t$.


What is the purpose of a single input, single output, bidirectional shift register? (source: edu.au)
This is the sort of bidirectional shift register, I'm talking about.
I understand why the normal right shift is useful, but when you shift it left, all you're really doing is sending the data input straight to the output.
Is there a useful reason for shifting bits in this manner?
EDIT-
I'm trying to understand how the when shifting to the left, the value int left most register is outputted at the right most end. It makes no sense.
Shouldn't the output be what the input is when shifting left?
Thanks!

a) if during left shift the output signal immediately followed the input, output changes were no longer synchronous. (And the circuit would just act as a "buffer".)
b) when you shift it left, all you're really doing is sending the data input straight to the output no:
it shifts the FFlops' data right to left, capturing Input data in the rightmost one (the one driving Output data, clocking Input data straight to the output ). All but the latest capture become observable again when you switch to shifting right and shift, only.


Why is the language of even-length non-palindromes context-free? We know $L_1=\{w_1 w_2 \in (a+b)^*\mid |w_1|=|w_2|, w_2 \neq w_1^{\;\mathrm{R}}\}$
is a context-free language.

Can anyone help me produce a PDA or give me any hint how I can quickly understand why this is context-free?

The language of even-length non-palindromes is given by the following context-free grammar:

$$S \rightarrow 0S0 \mid 1S1 \mid D$$
$$D \rightarrow 1A0 \mid 0A1$$
$$A \rightarrow \lambda \mid 00A \mid  01A \mid  10A \mid  11A$$


Asymptotic analysis of statements I was wondering if you could double check on the following statements being true, false or non-conclusive (as in in some cases true, but false in others). Here they are:

1) $F(n) = \log (n^n)$ implies $F(n) = \Theta(\log n)$.

Answer: It is a tough one? It is confusing because of $n^n$. My assumption would be to have it as non-conclusive. It is because for some cases, where $n$ is even a bit large, $\log$ will greatly decrease $F(n)$'s value. For abysmally large numbers, it will be significant, i.e. $n = 10000000$. Maybe I am wrong?

2) $F(n) = n \log n + n^2$ implies $F(n) = \Omega(n \log n)$.

Answer: True. We drop $n \log n$ (since it is not significant) and indeed $n^2$ will grow asymptotically faster (it is slower) than $n \log n$.

3) $F(n) = n!$ implies that $F(n) = O(2^n)$.

Answer: False. $n!$ grows faster than $2^n$. Therefore it would be $\Omega(2^n)$ not $O(2^n)$.

The function $\log(n^n) = n\log n$ grows much faster than $\log n$, so we can conclusively say that $\log(n^n) = \omega(\log n)$. It even grows much faster than $n$, so $\log(n^n) = \omega(n)$.

You say that whether $\log(n^n) = \Theta(\log n)$ (where perhaps you mean $\Theta(n)$ instead of $\Theta(\log n)$) is "inconclusive", since for small $n$ there is one behavior, and for large $n$ there is another. For asymptotic analysis we care only about the behavior for large $n$.


Does word addressable memory have more bytes than byte addressable memory? Well, my question - if word addressable memory has more bytes than byte addressable memory - is derived from the fact that in word addressable memory each address addresses a word and in byte addressable memory each address addresses a byte.
In the case of word addressable memory - If the word size is 4 bytes 32 bit architecture, for example, do i have 4*2^32 bytes in my memory?
And in the case of byte addressable memory -will i have 2^32 bytes in my memory?

How is it possible that the same ram, i.e given the ram size is 4 GB, would contain different number of bytes depending on byte/ word addressable memory?

1GB RAM has 1*1024*1024*1024 bytes in it. Say our architecture is 32 bit. So in the case of byte addressable memory there will be 4*1024*1024*1024 virtual addresses per program but in reality there are 1*1024*1024*1024 physical addresses, each points to a byte.
In the case of word addressable memory there will be 4*1024*1024*1024 virtual addresses per program - each address points to a word? So in this case there will be theoretically 4*4*1024*1024*1024 bytes available for each program ?
There will be 1*1024*1024*1024 physical addresses, each address points to a word. So there are actually 4*1*1024*1024*1024 bytes in the memory in this case?

As you can see I am super confused.

If you had a byte addressable architecture where pointers have a fixed size, and every or almost every bit pattern is a valid pointer to a distinct byte address, and a word addressable architecture where pointers have the same fixed size, and every or almost every bit pattern is a valid pointer to a distinct word address, then the second architecture could address more memory. Which means you could buy more RAM for more money and put it into a computer and use it.

That second architecture would be in big trouble with lots of data structures that require byte pointers, like typical implementations of strings, compressed data, etc. Writing an mp3 player with word addressable memory wouldn't be my kind of fun.

In practice, even mobile phones are using 64 bit processors with pointers taking up 64 bits of memory, and the addressable amount of memory right now so much exceeds what anyone could reasonably pay, that it just doesn't matter. 4 GB of memory cost around 20 dollars, multiply by 4 billion, that's 80 billion dollars, and that's what you can address with byte addressability and 64 bit pointers.

(An analogy: You have an order form that allows you to order boxes of eggs. There are only six digits space, so you can order at most 999,999 boxes. If you order boxes of 18 eggs instead of boxes of 6 eggs, you can order three times as many eggs. You also pay three times as much money. Now you look at your form and it has space for 20 digits. That's more than the whole worlds egg production, whether you order them in boxes of 6 or 18. )


No. of disk blocks writes required for writing the file Assume that a file is written using write(fd, buf, K) system calls, where fd is the file descriptor, and K, the number of files to be written to the current file offset which is a multiple of the disk block size D. The total number of disk block writes required to be executed before the system call returns is:

(a) is equal to K/D

(b) is less than K/D

(c) is greater than K/D

(d) None of the above.

In my opinion, the answer should be (c). But the solution manual says it's (d).

I believe the number of file writes required for writing a file is $ceil(K/D)$
So, the answer should be (c).

Am I correct? If not, what am I doing wrong?

Thanks in advance!

The correct answer is: greater or equal to K/D, depending on the fact that K can be a multiple of D or not. So, the answer is actually c), which differs from the other three answers.

Note that if there were an answer “ceil(K/D)”, that would have been the correct answer.


How to prove the linear context free languages are closed under gsm mapping? I'm stuck on the following question:

How to prove the linear context free languages are closed under gsm mapping?

If you know that gsm mappings can be written as a composition of an inverse morphism, intersection with a regular language, and a morphism, then it suffices to observe that the linear languages are actually closed under these operations.


Regula falsi with error in x-axis I want the regula falsi to get x +- .0001 so that f(x) = 0. But all the implemetations I see get x so that f(x) +- .0001 = 0 which doesn't make much sense. (f(x) = x^3).
How do I  stop the regula falsi method when the error is .0001 on the x-axis?
I have this scilab code:
function salida = falsaposicion(fun, tolerancia, a, b)
   deff("y=f(x)", "y="+fun);
   if (f(a)*f(b)>0) then
       disp("Error");
   end

   cAnt = 1e100
   c =  b - f(b)*((b - a)/(f(b) - f(a)));

   while 0 == 0
       if f(b) - f(a) == 0 then
           disp("Error");
           break;
       end

       if abs(f(c)) < tolerancia then
           break;
       elseif f(a)*f(c) < 0 then
           b = c;
       elseif f(b)*f(c) < 0 then
           a = c;
       end

       cAnt = c;
       c = b - f(b)*((b - a)/(f(b) - f(a)));
   end

   salida = c;
endfunction

disp(falsaposicion("x^3", 0.0001, -6, 3));

```

A loop invariant of regula falsi is that $f(a)f(b)<0$. Under the assumption that $f$ is continuous, this implies that there is a solution $x_0$ of $f(x0)=0$ inside $(a,b)$, since the eventual output $c$ is also in $(a,b)$, then for any output you have that $|c−x_0|≤|a−b|$. Therefore, you can add to the breaking condition, instead of it being abs(f(c))<tolerancia, to be abs(f(c))<tolerancia and abs(b-a)<.0001, or replace it completely by abs(b-a)<.0001.
It is true that the distance between $a$ and $b$ doesn't always go to zero. That's the price you pay for converging faster than bisection in some cases. Still, that is the only condition that you have to bound the error, if regula falsi is applied by itself, since $c$ could be approaching a root only from one side. What people do is not to apply regula falsi by itself, but to mix it, among other methods, with bisection. For example, what is done in Brent's method.


Largest sum divisible by n I asked this question on StackOverflow, but I think here is a more appropriate place.

This is a problem from Introduction to algorithms course:

  You have an array $a$ with $n$ positive integers (the array doesn't need to be sorted or the elements unique). Suggest an $O(n)$ algorithm to find the largest sum of elements that is divisible by $n$.

Example: $a = [6, 1, 13, 4, 9, 8, 25], n = 7$.  The answer is $56$ (with elements $6, 13, 4, 8, 25$)

It's relatively easy to find it in $O(n^2)$ using dynamic programming and storing largest sum with remainder $0, 1, 2,..., n - 1$.

Also, if we restrict attention to a contiguous sequence of elements, it's easy to find the optimal such sequence in $O(n)$ time, by storing partial sums modulo $n$: let $S[i]=a[0]+a[1]+\dots + a[i]$, for each remainder $r$ remember the largest index $j$ such that $S[j] \equiv r \pmod{n}$, and then for each $i$ you consider $S[j]-S[i]$ where $j$ is the index corresponding to $r=S[i] \bmod n$.

But is there a $O(n)$-time solution for the general case? Any suggestions will be appreciated! I consider this has something to deal with linear algebra but I'm not sure what exactly.

Alternatively, can this be done in $O(n \log n)$ time?

Here are a few random ideas:

The dynamic-programming algorithm can be flipped to look for a smallest sum instead of a largest sum. You just end up looking for a sum congruent to the remainder of the sum of the entire array, instead of one congruent to zero. If we process the elements in increasing order, this sometimes allows the dynamic algorithm to terminate before processing the entire array.

The cost would be $O(n k)$ if we processed $k$ elements. There's not a lower bound of $\Omega(n \log n)$ on this algorithm because we don't have to sort all the elements. It only takes $O(n \log k)$ time to get the $k$ smallest elements.
If we cared about the set with the larget size, instead of the set with the largest sum, we might be able to use fast-fourier-transform-based polynomial multiplication to solve the problem in $O(n (\log n)^2 (\log \log n))$ time. Similar to what's done in 3SUM when the domain range is limited. (Note: use repeated squaring to do a binary search, else you'll get $O(n k (\log n) (\log \log n))$ where $k$ is the number of omitted elements.)
When $n$ is composite, and almost all remainders are a multiple of one of $n$'s factors, significant time might be saved by focusing on the remainders that aren't a multiple of that factor.
When a remainder r is very common, or there are only a few remainders present, keeping track of 'next open slot if you start from here and keep advancing by r' information can save a lot of scanning-for-jumps-into-open-spots time.
You can shave a log factor by only tracking reachability and using bit masks (in the flipped dynamic algorithm), then backtracking once you reach the target remainder.
The dynamic programming algorithm is very amenable to being run in parallel. With a processor for each buffer slot you can get down to $O(n)$. Alternatively, by using $O(n^2)$ breadth, and divide and conquer aggregation instead of iterative aggregation, the circuit depth cost can get all the way down to $O(\log^2 n)$.
(Meta) I strongly suspect that the problem you were given is about contiguous sums. If you linked to the actual problem, it would be easy to verify that. Otherwise I'm very surprised by how difficult this problem is, given that it was assigned in a course called "Introduction to Algorithms". But maybe you covered a trick in class that makes it trivial.


Mathematical Induction Problem from Concrete Abstractions This is a problem from 'Concrete Abstractions' which is available free on the web[1]. It's a book similar to SICP. The problem:

  Exercise 2.16
     Consider the following procedure foo:

(define foo
  (lambda (x n)
    (if (= n 0)
        1
        (+ (expt x n) (foo x (- n 1))))))

  Use induction to prove that (foo x n) terminates with the value
          $$\frac{x^{n + 1} - 1 } {x - 1}$$

  for all values of x != 1 and for all integers n >= 0. You may assume that expt works
     correctly, (i.e., (expt b m) returns $b^m$). Hint: The inductive step will involve some algebra.

I've watched a video on induction on Khan Academy and read the induction material in the book, but I can't connect the dots to solve this problem.

Edit:
I am stuck at the Inductive step. My work:
Base Case:

(foo x 0)
(if (= n 0)
    1)

returns $1$ and

$\frac{x^{0+1} - 1} {x - 1} = \frac{x - 1}{x - 1} = 1$

So for the inductive hypothesis: Assume (foo x k) terminates in $\frac{x^{k+1} - 1}{x - 1}$ for all $k \geq 0$. Then for $k+1$:
I essentially add $k+1$ for the assumed formula above, so:
$\frac{x^{k+1} - 1}{x - 1} + k+1$. What I get is a long equation that I have no idea what to do with.

Your induction step is recorded incorrectly.

You wrote:

$$\frac{x^{k+1} - 1}{x - 1} + k+1$$

You should have written:

$$\frac{x^{k+1} - 1}{x - 1} + x^{k+1}$$

Basically, you are proving the formula for the sum of the geometric sequence.